Apple Mail.app does not play the new mail alert sound in a consistent manner, and this bug has been there since the first release of 10.5. This occurs when Mail.app uses IMAP's IDLE command to discover a new message -- if that's the case, then the new mail alert is not played. The alert is only played when Mail.app uses the periodic polling to discover a new message.
Therefore, the solution is to turn off the IDLE command, and make the polling interval shorter. In Mail, open Preferences and go to Accounts » Advanced in all your mail accounts and turn off the Use IDLE command feature. Next, go to the General section of Preferences, and set Check for New Mail to Every minute -- you can set a longer interval if you want, so long as you don't set it to Manual.
Now your mail alerts should play for every incoming message, but you will see your messages up to one minute later than you would with the IDLE mechanism.

