On second thoughts, how about this (not so elegant) approach:
1) Your consumer(MDB) identifies that the external system is down
2) This MDB will schedule a job(which will start 5 min from now) using a Scheduler(there are open source schedulers like Quartz which you can use). The MDB will pass the message(which it received in its onMessage method) as a parameter to the scheduled job.
3) The onMessage method of this MDB will return normally, so that the message is removed from the queue and will NOT be redelivered.
Now after 5 minutes, the scheduled job is invoked and it receives the message as the parameter. The responsibility of this scheduled job will be to put the message back to the original queue so that it is delivered to the MDB by the server.
I cant say what all issues you might encounter while trying to get this working, since i haven't tried this sort of a thing myself. Also this does not look like a elegant solution to me - you can add this to those "weird" implementations, which you mention, you have already seen.
I would rather prefer the application server providing me a feature like "redelivery interval" for redelivering the messages.