Growl with the GrowlMail plug-in work great in notifying me of new messages for any of my accounts (various POP. IMAP and .Mac) in Mail.app.
Growl doesn't support Mail.app "out-of-the-box" (er, vice-versa -- Mail.app doesn't support Growl natively), so you need to grab the GrowlMail plug-in to use with Growl from here:
http://growl.info/applications.php
Of course, the mail has already arrived and has been downloaded when you get the Growl notification -- which doesn't exactly meet your specific needs, but is the best I can come up with at the moment.