Looking for better search functions in an email client

Question

Gmail's web interface has some serious search issues:

• Labels are applied to messages, not conversations. The search for

  label:foo -label:foo

will return conversations where there is at least one of each. Most of the time this is not a win.

• There is no way to restrict a search to finding all terms in a single message. Near as I can tell, any search is done against every message and the results OR'd together.

• There is no way to restrict a search to the messages that you didn't write. E.g. I want conversations where the other guy said "baz" but I didn't.

• There is no way to sort the list other than by the most recent time stamp. I'd like to be able to sort by first time stamp, by latest 'not-me' timestamp

• There is no way to show conversations where I'm not the last correspondent.

---

I cannot be the only geek who loves gmail's filters and labels, but wants additional functionality.

• All conversations with label foo on at least one message, but no message with label bar.
• All conversations with a single message that contains both "branch" and "twig"
• All conversations with label foo where I was NOT the last correspondent.
• All conversations where the first message in the string is over 1 year ago. and the last message in the string not by me was less than 2 months ago.
• Conversations with label foo where the last message not by me has more than 100 words of non-quoted content.
• Ability to store frequently used searches.

I am open to the following options

• A web client that uses gmail as a back end, and works through api calls.

• A dedicated client that runs on MacOS.

• A Client server combo that downloads email from any arbitrary server and allows me to accomplish this locally. Client portion either via web interface. Server on mac or LAMP.

Other combinations that don't include Microsoft considered.