What Android geocaching apps have you tried? I believe all of them (CacheMate, GeGeo, GeoBeagle, Geocacher, Geodroid) can do live searches based on your location. Of course, these are all web-based searches. Groudspeak will eventually release an Android app with direct database access. There are other apps in the works as well. CacheMate has by far the most functionality of any existing smartphone geocaching app.
I've used CacheMate on WM devices since almost forever. I haven't tried any of the Android apps yet as I'm still waiting for the new device to arrive. However, I'm not sure you get my point. For any of the apps you mentioned to work properly, I still have to create and download a pq based on my current location. What GCz II does for me is allow me to simply tell it to get me nearby caches and it does. No planning, no filling out pq forms, no importing gpx files from emails, etc. It allows me to post logs directly from the app as well. I'm not sure if there's anything that easy to use for the Droid OS...
---edit---
My understanding is that the author of GCz II is looking at the possibility of porting to the Android. I'll certainly post here if that happens.