I suffered from the same problem, a couple of months ago.
It took me like two weeks or more to find out that I wasn't able to
receive sms anymore.
When I figured it out I called fido, they sent me an SMS that had the
effect of pushing every other one pending... I then found out that I
had 50 voice mail messages (since Fido uses a very archaïc and stupid
way of alterting you when you have voice mail... unlike the rest of the
world who actuallly use the GSM alert...)

I suspect their voicemail-sms-sending app to be of a potential source
of problem; since, if I recall correctly, it will only send you an SMS
when you're phone is on, alerting you only once even if you received 5
voicemails (as long as your phone was off all that time.) So there's
something that waits until you're on and sends you an sms (you don't
get an sms-per-voicemail automatically.) So that kind of working around
could be a source of problem, although I have no real clues.