They normally can accomodate for that, but they don't show you pricing on their site. Basically, you'd have to contact them and talk about your specific needs. But I don't believe companies like Mailchimp, Aweber, and SendGrid would turn you down.
Yep if you contact them directly you can get direct pricing on any sized list. If you contact me (emails in my HN profile) I can put you in touch with our guy lance at Mailchimp
(Make sure to put your email in the about box, otherwise it is hidden)