Another method (if any downtime at all is absolutely unacceptable to you), is to use Postfix or similar as basically a delayed relay.
You could start a server as a relay, and then configure the scan threshold to be something very high (and keep expanding it if your maintenance window grows, which they often do :p ). Alternatively, you could firewall-block any outbound relay/send attempts in such a way the Postfix (or whatever) would requeue the messages.
Network/DNS wise, you'd set up a relaying/delaying server as mentioned above, point your old MX record to it (with the TTL reduction as mentioned by @Paul), conduct your maintenance, point the MX record back where it should go, change the relayhost in Postfix to point to that record (it might get annoyed because it thinks it's pointing to itself, in which case you'd need a second temporary MX), and let it process the queue.
That was a bit fragmented as an explanation. For more information, check out this ServerFault question and this how-to. That should get you on the right path.
Then again, if a little bit of downtime is acceptable to you, @Paul's solution is much simpler.