First, some version info: this issue started with (I believe) 2.0.0.0-4, and has persisted across the upgrade to 2.0.0.4.dfsg1-1. Both of my instances of icedove access mail from the same IMAP server (though my laptop is often suspended).
The problem:
When I upgraded to 2.0.0.0-4 (I believe), the new email notification OSD was turned on. This seemed very useful, but has descended into the utmost of uselessness. Whenever I receive a new email, the dialog pops up the _same 4 messages_ that it's shown me, as far as I can tell, since the first set it decided on when it was started most recently.
One potential cause of confusion (for Icedove) is that I have it automatically move certain new IMAP emails to IMAP mail folders, so it may "lose track" of them for the purposes of determining when they have been read and should no longer be displayed.
This problem is mirrored on my laptop, and has occurred with both 2.0.0.0-4 and 2.0.0.4.dfsg1-1 as well. Unlike this box, which takes care of all of my email sorting and junk filtering, my laptop doesn't move emails. It is thus very odd that icedove displays notifications for emails that are no longer in INBOX (which is, to say, those new emails which used to be in INBOX, but were subsequently automatically moved by my desktop).