What to do when 'dpkg --configure -a' does not work?

I recently had trouble with a MySQL installation in Ubuntu. For some reason or the other, during an upgrade to a newer version of mysql-server, the upgrade script had issues stopping the server and the script failed. This meant that apt could no longer function as it kept raising a red flag over the broken upgrade with the following instructions:

Unfortunately, the above command too failed as the script could not stop MySQL (again) in order to proceed with the upgrade.

Stopping MySQL database server: mysqld failed!
invoke-rc.d: initscript mysql, action "stop" failed.

While I could have investigated why mysql could not be stopped (manually killing the process did not help), I wanted an easier route as I was happy to simply nuke mysql (I had a database backup) and reinstall it. I could of course not use apt to do so as it was being anally pedantic about the broken package. So, I had to brute force it. This involved:

(Actually, I used dpkg --purge --force-all mysql-common mysql-client mysql-client-5.1  mysql-server mysql-common mysql-server-5.1 mysql-client-5.1 mysql-server-core-5.1 which broke some dependencies, but was necessary. I then also renamed the /var/lib/mysql and /etc/mysql directories.)

Once I had forced the uninstallation, I was able to proceed with the mysql install to reset my system back to pristine goodness.