The periodic "restarting search" thing is a basic way the matchmaking system in Halo's 3 and Reach functions. It (usually) has nothing to do with connection issues. I don't know exactly how it works in the overall scheme, but this is my guess:
The matchmaking system works by trying to lump people into groups, and getting a match going when a group reaches a sufficient player count. But with how it lumps people up, it's entirely possible for the matchmaking system to be tracking two in-progress groups of, say, 10 people, in a playlist like BTB where 16 people are required to get a game going. Clearly there are enough people to get a game going, but these groups are not fully combinable (since combining them would result in a group of 20). Also, since the algorithm has to ensure complicated player groupings (like parties) work out, and to minimize the number of things that need to be tracked by the server at once, they decided for simplicities sake that they couldn't just pull people from one group and drop them into the other. So, the resolution to the issue is to break both groups up and re-sort them.
It's quite common to go through several restart cycles. Though, if this is REALLY bad right now, it could be sorting difficulties or something on server side, I guess.
[Edited on 07.08.2012 8:59 PM PDT]