Used to happen to me all the time. Wondering if I got any Facebook messages, log on, spend half an hour wandering through the news feed. Big time suck.
I'd guess this is why they're sending message notifications only sporadically? I've been thinking of setting up a little service for myself to monitor the FB web interface messages and then forward their content by email so I never have to look at the damn thing.