To double check, have you checked every NPC house you've built that has NPCs in them?
If you have a pylon network and NPCs spread throughout different biomes, he won't always spawn in what you may consider your main base. He'll randomly spawn at different NPC houses. As a result, all of them need to be checked.