For kde I like kbiff the best (or sometimes I just use a karambatheme that shows me that there is mail in one of my boxes but that doesn't really notify me by a popup or something else). For gmail I use the extension of firefox.
I think it depends on the kind of mailboxes you have. I have a couple of pop3 accounts on an external server (the one of my internet provider) and for me the only one that really did the job good was kbiff. I tried others as gnubiff or mail-notification but they didn't work really good (mail-notification didn't work at all; but that may have changed because it's already a couple of months ago I've tried them). I only tried the ones that can dock in the system tray and never found one that works good for gnome. So I think it's an interesting thread.
Ps: sorry for my bad English