The excuses that have to be made to make the "SAGA" work have always bugged me. Worst one to me is why the hell does Obi Wan have to be such a lying a-hole to Luke about his dad. But anyway...

Trying to play along with the way things are in the movies, it doesn't make my head explode to imagine that Death Star II is completed much quicker than version I. Prototypes are often held up by (among many things) the building of tools that need to be invented to actually build the prototype. Once one is built, however, all these things are worked out and building a second is often twice as easy --or easier. (It is also possible that DS II was being built all along-- if one Death Star is enough to rule the galaxy, then Sidious might likely think that two is twice as good).

So if we look at the real world and see how long prototypes can take compared with production models, then the long development of Maul/Grevious may actually be useful to the Saga. After all, how did Sidious become such a masterful cyborg-maker as to rebuild Anakin in what seems like a few hours? Maybe he had years of practice developing General Grevious.

Just thoughts-- I wouldn't put any of these explanations into the movies. They're more like the kind of stuff that should make sense "when you think about it". The whole Saga really works better for me when I let it remain just a little out of focus.