I have an a few machines that I was planning to run in a cluster, but have decided after some testing to configure them differently. The partitions and Ubuntu install are still as I want them, but it would be nice to have them back to a clean state without having to re-install them all.
I actually had to do this a while back (a couple years ago, so excuse the not quite perfect commands) and this is what I did.
First:
I then happened to have a fresh installation around that I did the same thing on. If you don't have one, you could probably find a list somewhere for your distribution. Then:
The second sdiff is to allow for default packages you might have removed from your installation. Just wanted to avoid more errors then necessary. The next part is really whatever your favorite method for search and replace is, I like vim so that's what I used.
This is because the dkpg leaves the install word after every package in the list, and we don't want that. I also ran a couple more commands in vim to remove excess white space and replace the line breaks with spaces, just to make it a bit cleaner. You then run this file through apt-get remove (add in --purge if you want).
If you want to be extra thorough you can use different cleaners to get rid of crap, and also run the comparison differently so you can add the packages back that you may have removed [from the default package list].
All in all, after I did all that I decided it wasn't worth the effort compared to the relative ease of reinstalling Ubuntu.
And then, if something was broken, run a couple of times: