Have you verified that all of your IP settings on the server are correct? DNS, WINS, etc?
I just checked some things on my R5 server, and I don't see anything that really stands out.
From your description, it sounds like the notifications are being sent when the server boots, and then additional notifications are queued and never sent.
I would definitely think about calling support on this one.