For my application (which has about 24,000 downloads) I am seeing an average of of about 1300 messages sent a day.
Those are low numbers, but then my client base isn't that large either. But I figure I might as well contribute some info. :-)
My notification provider is idle most of the time so there is MUCH more capacity available if I need it.
Its also using very little ram at this point (somewhere around 13 mb - I implemented my provider in Python and suspect most of that is taken up by the run time).
I am running on a Media Temple dv (specifically the Base configuration).
I haven't extrapolated out the numbers to find what my theoretical maximum would be, but because of the niche market of my application its not something that worries me at this point. I have lots of capacity to scale with.
Hope that helps a bit.
chris.