We're using Campaign Monitor and its faaaar too expensive. Sending 40k/mo would cost over $400/mo and thats ridiculous for email. Mailchimp and others cost pretty much the same.
Are you sending to 40,000 different email addresses or sending a total of 40,000 emails per month? If you are sending to 10,000 addresses 4 times a month (for example) then take a look at iContact. 10,000 subscribers 6x a month would cost $74 a month.