Don't forget that if Perrin sent out the Asha'man to find Rand after they had a few days of rest (ie: a few days after his last POV in TGS), this would have taken place a few days after Perrin had seen Rand at a Tairen manor (ie: right before the KOD false Tuon trap) and then during the few weeks when Rand was moving almost constantly and hiding. He settled at one place and let Rhuarc know to come to him etc. a few weeks later only. It's very doubtful the Asha'man would have managed to find Rand during those weeks and before he moved to Bandar Eban. The best information they could get (from Darlin in Tear for example) would be : "he's somewhere in Arad Doman and he reaches us, not the other way around". After failing for weeks to locate Rand in AD (countryside hideouts), the Asha'man may have given up and returned to Perrin.

It's doubftul it's what happened, though. We've seen messengers Rand had sent to Tear reporting back to him (I mean, we know what they reported). Rand would have heard that Perrin has been looking for him at the Stone of Tear then.

As for "a better solution", we actually don't know what Perrin has decided to do in the end. His POVs stopped before the Asha'man were rested enough to Travel. We can tell that at that point, on the moment he was told how long it would take the two Asha'man to send all the groups of refugees home, Perrin has not considered a solution involving Rand, but we have no idea what he decided to do in the end.

There's an apparent plot hole there. In KOD Grady had taken to tie up his gateways because he was exhausted. It's conceivable that Neald and him forgot to do that during the hunt for Faile, or thought it too dangerous (ambushes/sneak attacks by Shaido etc.) not to stay in control of the gateways at all time and so ended up exhausting themselves over the 60 days or so (they alternated making a big/prolonged gateway each night to travel to the last point the scouts had spotted the Shaido trail during the day), but it's hard to explain why they don't simply use tied-up gateways for the refugees to avoid exhaustion. It's not like they need to drop each of them on their own doorsteps and make thousands of trips. They can dump all those within a few days of Cairhien at Cairhien, and those living near Maerone at Maerone and so on, and instead of leaving the gateways open and channel for very long each time, they could tied them up instead. We're speaking of a few hundred gateways to make, at most. It should take a few days, at most. Balwer's calculations seem rather based on the maximum length of time the Asha'man can afford to leave gateways open each day and how many refugees will be able to pass through in that time. There's no doubt RJ was setting things up for Perrin's Asha'man to be exhausted (it's all over his storyline in KOD) and unable to Travel for a while, but the whole refugee vs. Travelling problem sounds like it could be an addition by Brandon. This could mean it's a "false issue", ie: something will happen soon and Perrin won't be sending out the refugees after all, it's just something Brandon came up with to have an issue to discuss in the Perrin "teaser" chapters in TGS (and while doing so, he forgot about tied-up gateways).