I'm not sure if you're planning on using Sendmail or (better yet) Qmail, but in either case you should be able to configure mail2 as a relay-only mail server.
For example, when mail2 (for whatever reason) receives an incoming message, it simply relays/forwards it to mail1. Of course if mail1 is down, mail2 would simply queue the messages for a configurable amount of time.
Now, if the end user is unable to connect to mail1 to *retrieve* their mail, redirecting them to mail2 would not work in this case (since it would be a relay-only server with no POP facilities). But they can rest assured that their mail has in fact been accepted...
Another option, if both machines are in the same facility (which I'm guessing they aren't, given your bandwidth concern), would be to use ip masquarading/forwarding. Actually I think this could be done remotely as well...
You could set up a gateway box. Its IP (externally accessible, eg a public IP) is what the users are given. For example, mail.domain.com points to an IP on the gateway. The gateway's only function is to be a gateway (plus firewall if desired).
Now, say you have two mail servers both behind the gateway box. mail1 and mail2 each have an internal IP.
The gateway runs a cron to periodically check mail1. Normally, gateway forwards (via ip forwarding) all port 25 and 110 requests to mail1. If the cron detects that mail1 is down or inaccessible, it updates the forwarding rules to point to mail2 instead.
Perhaps (via NFS or coda) you could have a fileserver hold the mail centrally, where the POP/SMTP servers do not actually store data...
Anyway, the ip forwarding can be done easily enough with ipchains and the ipmasqadm family of tools; For example, I forward all requests on port 7777 to my sometimes-windows box for Unreal Tournament games on my home network

This could very easily be configured to automatically switch, and I believe you can in fact do this with external IPs as well (eg, mail servers in separate facilities).
Now, OTOH, if the network leading to the gateway box is down... that will break the whole system even if mail2 is perfectly accessible...
Just a thought anyway
<EDIT>
Further thinking... suppose you set up mail2 as the actual gateway box as well. If mail1 is okay, forward the requests on to mail1, and mail2's mail system is not touched. If mail1 is down, however, mail2 accepts the mail itself until such time it can forward them to mail1...
Something like this will require a lot of planning/thinking to make sure everything has been considered. I'd be happy to ponder this some more, given the following:
- What OS and mail software are you using/will you use?
- Is a third gateway box out of the question?
- Are they to be in the same facility?
</EDIT>