I found searches complete faster* and more accurately if you pan and zoom the onscreen map closer to the destination.

* Edit: I just tried this and cannot confirm it to be true. I swear it helped me with results at one point. Please let me know if this actually works... Or if it doesn't.

I've found CoMaps to be slow too. Not sure if it's just the nature of the beast (local large database searches will just be slower than contacting a hyper optimized Google server) or specific to them vs alternatives though. I haven't tested other OSM based apps to compare.