I gave up on Versamail early on. It works for some people; not for others. I also tried GopherMail and Snappermail (also very popular). I eventually went with Chattermail and an account on Fastmail and have had zero problems (but I also don't really need "push" email the way I had it on my Blackberry) I use Chattermail to get emails from my POP3 account, my Gmail account, and two Hotmail accounts.
I think the "must have" apps depend on what you use your Treo for. If you like, I can give you the names of the apps I use and why I decided on those and not others.