On the search issue, apparently Power Search from X-Phone Software can search everything well. I haven't tried it.
On other stuff, I've just been posting a bunch of comments in a
parallel thread. In particular,
a post on calendars lists three betas out that are good palm replacements (particularly pocket informant),
a post on sync options including a web site with a comprehensive list of options and a recommendation to try the free "my phone explorer, and
a post on notebook options including a palm-like option based on simplenote (cloud) + Jade Note (android) + Resophnote (pc).