That depends on your implementation. But even if you keep waiting, it should be in a routine (so you don't block), so indeed AddSearchMessage should return. When you wait in a routine, you should have concrete rules when to exit it (e.g., when threshold of two matches is achieved), otherwise your gossiper might end up consuming memory until it crashes.
Regarding the callback, you are free to do it as you prefer, the only restriction is that the callback expects a gossip packet so you might need to craft one. We have added this piece mostly for you to be able to use the GUI, and there is no test checking it, so it is not a requirement.