Amazing costume!
It would have been costly and time consuming to do the optical work, but Grevious could have been done that way. He could have also been animated in Go Motion for the complex shots too.
This scene from Labyrinth was shot on a black backdrop, with the puppeteers also dressed in black.
http://www.youtube.com/watch?v=sU_6l1kwu7Y
"How they could have done the prequels with 80's FX" would make for an interesting thread? ;)