Are you using one of the native alerts already on the phone or a custom alert you put on the phone yourself? If you're using an alert that is saved to your memory card, it is possible that it may lag when reading the card to play the alert. I'm not sure if thats what it is but its definitely a possiblity, considering that it works fine immediately after a battery pull.
Are you by any chance typing or touching the screen when these messages are coming in? If so, be aware that when the device detects an input from the screen, it'll mute ANY notification sound.
No, I'm using a factory sound for the alert, and this happens at random times. Sometimes it'll be sitting on the desk next to me, sometimes in my shirt pocket, so I don't think touching it could be the problem.
