Getting more specific
Now that I am home instead of at work, and have my Manual of the Planes handy, and my Book of Vile Darkness, I can better articulate my suggestions.
I reccomend using Corrupt Anarchic Elementals with tweaked weaknesses. This will translate into Elementals with some Fast Healing, improved damage reduction, a handfull of extra immunities, improved AC, and improved damage (Corrupt creatures have their damage dice upped by one category). In addition to using Elementals, you could also apply the Corrupt Anarchic, and Element templates to non-elemental monsters just for variety.
For your sanity's sake, I suggest creating one 'meta' template from the Corrupt and Anarchic templates and another for the previous two + the 'Element' template so that applying the templates becomes easier.
Creatures that would be intresting to apply this template to would be Giants (just for the beefy reach and str), Giant Insects of all sorts, Sharks (just think of your players faces whe you tell them a large flying, great white shark made of green burning fire is coming after them), Owl Bears, Gryphons, Wyverns, and Trolls.
I see this as a great opportunity to get creative with the descriptions. Flames that burn wrong, skin made of corroded metals, and creatures existing outside their traditional elements.
As for the villian creature, I would probably suggest a Kraken with class levels and some of the above templates. Tentacles on a great evil beast can never be a bad thing. Especially for a villain / monster type that is meant to be fundamentally wrong.
END COMMUNICATION