MrInsaneA said:

Has anyone considered removing Grievous COMPLETELY from Revenge of the Sith?

It may be fairly simple to remove him from the opening battle. Anakin mentions "General Grievous's ship is dead ahead" but I imagine this wouldn't be too hard to remove. TheCutter did an edit where Anakin and Obi-Wan get away in the escape pod while the ship is being attacked. I thought it worked pretty well, and it avoids the entire confrontation with Grievous after they rescue Palpatine.

The appearance of Grievous on Utapau is more tricky. What exactly is Obi-Wan doing while Anakin is off falling to the dark side? It's troublesome to have him go after the never-seen Grievous. Maybe it could be arranged to have him looking for the Separatist leaders instead and have them escape to Mustafar while the clone army attacks. There are the couple times when Grievous is mentioned when Anakin is talking to Bail Organa and in a Jedi Council meeting. Perhaps these could be reworded or cut to refer the Separatist leaders or maybe the Viceroy instead.

EDIT: Along the lines of a resurrected Maul idea, TheCutter also did an edit with Duel of the Fates playing during the Obi-Wan-Grievous duel. It really improved the mood and could really sell the idea that this is Maul back from the dead. A good Maul impersonation could go a long way too.