Completely reproducable by me. Seems to be when you use the BB so it auto-locks on holstering, and pull it from the holster within a few secs (a minute?) of an IM message coming in. There's no icon on the (locked) home screen. Works if you lock it manually (or don't use it holstered).
RIM support finally said it's an OS bug to be fixed at some point in the future... I'm on T-Mobile UK's 286/291 release.