I just learned about imapsync, imapcopy, OfflineIMAP and Archivemail on linux. I haven't test them out yet. Have you tried any of these utilities? They seem to address the "Syncing on multiple machines" bit of your post.
I use mbsync (http://isync.sourceforge.net/mbsync.html) and mutt. The thing I hate is that Mutt's native OfflineIMAP support is broken, forcing me to use an external maildir syncer, but other than that, it works great. I still haven't set up search.