I've always had to restart after going through the four, because he shows the same four. Or am I just not observant enough?
I'm pretty sure that it's always the same four and you need to restart to get a different set.
If you go to someone's town and tell a villager that is in boxes to move to your town, what are the odds that they will or won't?
I bought a villager from someone and I told them to go to my town but I'm worried that they won't move.
Villagers you invite will always move in, unless you only have one spot and invite another villager (from someone's town or the campsite) after that. I think that the second villager to be invited gets priority over the previous one. I don't know if villagers from the void or StreetPass ever affect those chances, but I think that invited villagers get priority over them too. If you want to be extra safe, you can always switch off StreetPass temporarily. If you ever time travel, you can check whether that villager is really moving in by time travelling to the next day, when their plot appears.