Oh man, you sinner!

You talk of reasonable systems, and in the same breath you mention qmail! And you do not speak of Postfix.

In my mind, the main problem is not going to be the formatting of the messages, nor their queuing on the outbound exchanger.

To pump out a million or more messages, statistically speaking, all your outbound sockets will quickly be tied up on remote hosts that are out to lunch, overloaded and generally taking too much time to do nothing. This will kill your outbound delivery.

What you (the OP) needs to do is to set up two machines (or clusters), the first one attempts to deliver the mail at top speed. It performs one try, and one try only, with a very short timeout, 5-10 seconds max. If it fails, it hands the message off to a fallback relay that is configured to be much more lenient and patient at speaking to slow and/or broken exchangers.

This way your primary outbound exchanger is always available to send out messages, and doesn't get its deferred outbound queue clogged up with messages that might take minutes to deal with. Instead the fallback relay deals with the problem servers.

It helps if you NAT stuff out through the same IP address, so that greylisting servers don't consider the transaction as new tuple. If you can't then you'll need a third level of fallback relay. The second level makes a couple of attempts to deliver mail on the assumption that the remote server is spitting out transient errors due to greylisting, and only after it gives does it finally divert the message to a third-level fallback relay.

And naturally, this is simple to configure with Postfix :)