Powermail has always been blazingly fast, both in mail handling as in searching, and searches are highly customizable too. It still is.
Unfortunately, the developers have not been able to keep up with changing conditions. Powermail is still *terrible* in IMAP (it only supports one IMAP account at a time, and that one often crashes, while the handling is extremely poor if it doesn't crash).
Powermail does not fully support Unicode (you cannot write in Unicode), or html. Its text engine was developed in the last-century, and the unicode update of WASTE has not been used in updates of Powermail.
It is telling, too, that we're still at version 6 in October 2010. The folks at CTM probably just keep those customers who did not yet abandon them happy. Not the time to buy into it, then.
I've had versions 2 to 5, but passed on 6 (after a try-out). I would happily fork out the full price if it were up-to-date.