Deleting A Taxonomy breaks document creation

I have created a custom taxonomy, assigned some taxa from the taxonomy to some documents. I then deleted the taxonomy and found myself receiving this error every time i tried to edit a document or create a new one:

You are trying to access item that no longer exists. The most probable reason is that it has been deleted by another user.

I then tried deleting all the documents and found myself unable to add new documents, receiving the same error every time I attempted to add a new document. Thinking it must be that I'd orphaned some fields int he document edit forms, I removed all references to this field from the various config files that contained these references, but still am getting the same error.

The only way I've managed to get rid of the error is to create a new taxonmy programmatically with the same GUID as the one I deleted. At that point I can create documents, but if I delete the taxonomy I always get the same error above.

How can I delete a taxonomy without getting this error?