I can also attest to the high CPU usage, though I haven't been able to pin-point the exact cause.
Sometimes it can be fixed by forcing mail-notification to update, and other times it just keeps going on until I kill and restart it. I have 3 accounts: 1 POP, 1 IMAP and 1 Gmail.
I've been using the program for almost a year now and this has always been a constant issue, of such magnitude that it has forced me to go on a hunt for an alternative mail notifier on numerous occasions, but alas I haven't had much luck in finding something that similarly ties in with my workflow. I'm not sure if it's related, but I'm on a laptop (IBM T43) running Ubuntu (Feisty, and now Gutsy).
I can't believe the developers haven't bumped into this bug, as it pops up so many times it almost makes the program unusable.