Actually, I figured out why the links were still there. They were never actaully deleted. The Editor had moved the entire category accidentally to a different category. I thought he had deleted the category.

I simply returned the category to it's former place and everything went back to normal - but I was in quite a tailspin for two days.

Thanks for your suggestions!

Renee