The "correct" answer for high level 3.5 D&D play is that main Villains worth their salt will have access to a dedicated caster, if only via the Leadership feat. That caster, among other things, should have access to Craft Contingent Spell (CA p77). The villain should have an emergency escape button set to trigger whenever the party successfully implements scry & die tactics. Any plan that requires the villain to last more than a round when the party teleports in is a bad plan.
Given that we have a high level cleric who disdains time stopped gates gating in devils to crush their enemies, and who doesn't have access to psionics, and who doesn't feel like instant winning via Ruby Knight vindicator, the cleric can use miracle to manifest fission. Those fissioned clerics can then miracle (again), body outside body (Complete arcane), to have a coterie of 4 rather narcissistic guards each.
However, it's always worth having a backup backup contingent spell here. I recommend Summon Monster IX (with appropriate metamagics) crafted into a contingent form. This should be designed to summon (if you can meta-magic it) 1d3 (more! much more!) Malephants or a Bebelith Demon without metamagic. The "emergency duplication thing" is surprisingly hard to achieve on a short time frame.
If that sort of "everywhere on the battlefield at once" is a requirement of the character, the Ruby Knight Windicator combined with a way of leaving images of yourself behind. (Mostly worthless, as we'll expect the party to have true seeing at this point.).
Or, if one merely wants to summon backup, your pet caster can combine the spell Ice Assassin (Frostburn) which creates an exact duplicate of the target (with an unfortunate desire to slay the original) with Necrotic Cyst and Necrotic Domination (Libris Mortis) to provide absolutely dominated and loyal versions of the big bad. (Obviously, the big bad will have this pet caster under some sort of domination herself, else the pet caster becomes the big bad, and the current big bad is merely a figurehead.) Then, these absolutely loyal ice assassins can wait (playing poker) until they're summoned. Assuming that the villain avoids surprise, they can use a contingent celerity (PHII) to take a standard action, and summon clone Alpha, who can then repeat the process until the entire compliment of clones is available. Judicious use of short range teleports and contingent veils should make it somewhat difficult to figure out the original in the giant shell game that this will result in.