Same here, sorry to say. Yesterday I had a couple of notifications on my phone that hadn't come through to the Pebble, even though the Pebble app said the watch was connected. Rebooting the phone caused them to go through.
I think that having the watch periodically out-of-range of the phone's Bluetooth exasperates this behaviour. Obviously notifications won't come through when out of range, but they should start coming through when back in range, surely? At least new notifications, if not the ones stored up on the phone?