First, set a hard policy in place with your clients, define a hard maintenance schedule and make sure they are well informed that during those days & times, the server (or just their domain) will be offline to do maintenance.
Use a script to change out the error doc pages before the backup, then restore them afterwards...
Second, you could have a separate DNS server with the domains zone files pointing to different server where all the hosted domains have the 'Undergoing maintenance' page. When you are ready to do the maintenance, just shutdown the DNS on the main server. (can also shutdown Qmail and Apache, etc) All lookup requests should then be answered by the second DNS server. This is a more costly way to do it. And you should then also provide some sort of store & forward for the domain email during this time as well, else arriving emails may be kicked back as undeliverable.
There are many other options, these are just 2 that immediately come to mind. Hopefully others here will post additional ways which may fit your situation.
(Clusters/Farms/HotSwap Mirroring/etc)
Take a look at the 4psa backup solutions as well.