I'm using critsend.com - it's just "pay as you go", not a monthly fee. $1/1000, with discounts as you go up in credit purchases. I've had no problems with them in the last year or so. No - I take that back - the bounce stats data was 'lost' from my display for a couple days, but the retrieved it and added it back in. Happened once, IIRC - generally nice people, and there's an IRC channel for help if you want that (in addition to standard other help channels).
Tried critsend.com -- the service threw up random errors and didn't really work well for us. In the end, went with SendGrid. Though if you are sending <500 emails a day, using Gmail SMTP servers is the best option.
Postmark App (http://postmarkapp.com) has worked well for me in terms of sending large quantities of emails in the past. Easy integration, good team, active development.
I've just used PostMarkApp on a site, I love their interface, all works great but they only allow 'transactional' emails, which I guess is like 'click here to activate your account', whereas my site was sending out alerts to people (kind of like facebook does, but not as often), which they didn't seem to like too much.
Does sendgrid allow this? I've signed up to SocketLabs which seems to do it but haven't been able to get SMTP sending working correctly yet, haven't spent much time on it though.
For the record, the amount of hassles I've had with SMTP servers these services are very handy, especially for logs etc like postmark has
