In both Leopard and Snow Leopard, this is a known bug in Mail. Apple hasn't been able to fix it yet... and various other attempts at diagnosing the cause have also either only worked temporarily or outright failed.
I finally gave up trying to fix this an now use Herald. It is a sort of Growl popup notifier for new mail and it has its calls the OS X sounds if you want. Works perfectly.