Is it possible to automatically clear the database of redundant tables et al from previously removed modules / versions?

I thought running - http://www.yourdomain/update.php after installing your updated module did that?

"Automatically" no I don't think so, unless the module removes them itself (as they are supposed to, but isn't always the case). First be sure that you are using the module's uninstall if it has one. You disable the module, then (while its files are still in your modules directory) check the Uninstall tab of the modules page. Remove it there if it has the option, and only then delete the files. If you are updating a module (not deleting) then it is supposed to make all of its own database changes when you run update.php and if it leaves things messy, I'd suggest submitting a bug report.

However if all else fails, you can delete the rows or drop their tables using phpMyAdmin or your preferred tool. For instance if you have a row in the system table with that module's name, you can delete that row. If there's a new table created by the module you can drop that whole table. If the module made a block in the blocks table, you can delete the row which contains that block. Some modules may add entries also to the variable table. Those are (in most cases) the places a module will leave things. Of course it goes without saying... backup your database first, and only delete anything you are absolutely sure about (e.g. literally says a unique module's name).

-- David
davidnewkerk.com | absolutecross.com
View my Drupal lessons & guides

The Site Documentation module - http://drupal.org/project/sitedoc - might do the trick. It claims to list redundant blocks and tables and generate an SQL command which you can then run to delete them. I haven't tried this one myself, but the module maintainer's other modules are extremely helpful.