As you discovered, I don't think you can delete diagnosis codes if they are curretnly linked to a patient billing item. Unlike transaction codes, you can't make diagnosis codes inactive.
Can you edit the diagnosis codes you have? That would be the easiest.
Otherwise, I think you would have to find every patient with the stupid diagnosis code and change it, then delete the code.
Lytec should be able to find all references to a particular diagnosis code, if not, you could do an sql query with the pervasive database directly. Make sure you know what you are doing and back it all up first.