First off, regarding monsters in the ELH… I think the designers had good intentions in mind, but I think they really screwed some things up in terms of monster design by having so many non-unique epic monsters. When the “ordinary” monsters of that type are so powerful already, how much more powerful does a unique monster of that type need to be? So I never have, and likely never will, set the power level of a conversion based on something in the ELH. If you need a monster with 50+ HD, I say give it class levels or advance it normally.
The archfiends in the BoVD all have HD in their 20s and 30s. granted, this book came out before the power climb of 3.5, so that may be besides the point. However, I can’t think of a good reason to make Cerberus higher than the most powerful of the archfiends – but maybe it couldn’t hurt to put him in the midst of them.
I’m willing to go as high as 32-HD, 10 over my original estimation, but no more than that.