Comment 8 for bug 429841

This removed the package for me:

rm /var/lib/dpkg/info/flashplugin-nonfree.prerm
dpkg --remove --force-remove-reinstreq flashplugin-nonfree
dpkg --purge --force-remove-reinstreq flashplugin-nonfree