there: kudos to you for executing exact the idea I had as early as 2010! By any chance you could write an article on your experience with sells and marking? This is what most interests me! I am working on a project that will utilize Pushover so soon I will be a paid customer :)
Also, about your revenue model. How did you calculate that $3.99 would be sufficient to make profit AND give service to users on "all you can eat" terms? Wouldn't it be wiser to give one year for free (thats plenty of time to see whether I need and like your service or not) and then charge $9.99 per year after that? I mean, if this grows, I can easily see people eating up more bandwidth than this one-time $3.99 payment can bring into your pocket. If your TOS (sorry haven't checked) does not explicitly saying that in the future you may charge more, I think you may found yourself walking on a thin ice.
I don't really have much experience in the way of sales and marketing, but my integration efforts so far have just been to setup Pushover applications with icons ahead of time and then e-mail admins with the API key and some explanation so they don't have to do much work. I did the Github integration and Adium plugin myself to increase visibility.
I went with $3.99 because Prowl is $2.99 and Notify My Android is $3.99. I'm not convinced that a yearly service is worth the overhead and I personally wouldn't pay to use a notification app that had a yearly fee.
The bandwidth and server overhead for running such a service are pretty low and iOS/Android push notifications are free, so I'm not really worried about monthly costs for normal users outweighing the revenue the app brings in. Right now Pushover is running on one of my servers that does other things, so it's not even really costing anything tangible. If costs start to go up, I can always increase the price of the apps to slow growth (or increase revenue if it doesn't slow growth).