I recently had a 'situation' with dpkg that wasn't very fun to correct. I somehow lost my /usr/X11R6 directory (quit looking at me, I didn't touch it, honest! Don't you believe me?) apt refused to download any packages, insisting that they were installed, and dpkg wouldn't remove them, because it couldn't find them, but it still kept them in the installed package list. I tried dpkg --audit, but it didn't report anything. To make a long story short, I had to use a variety of dpkg --force options to make dpkg remove the packages, one by one. All of the X11 related ones. It was not fun.
I have a suggestion, if it's already been implemented in some form, I'm sorry for wasting your time. Basically, an option that will go through the list of installed packages, and check to see if the contents of the packages are actually there. If not, it could mark them for reinstallation, or something. I'm sure this could be used for other purposes as well. Maybe this is more of an option for apt-get, I'm not sure. All I know is that there should be something to help incidents like mine. Thank you for reading my message and promptly deleting it.
