in reply to CVS history woes

What would you do in this situation?

As you've discovered, this isn't really a technical problem. It's a social one. In the words of Martin Fowler "You can Change Your Organization or Change Your Organization." :-)

You need to get people to realise the damage that the mountains of shit are doing to productivity. I've found Technical Debt to be a very useful metaphor to use with non-technical folk.