I ran into the trouble that I needed to clean up some software built from source, that did not have the "make uninstall" option, what a mess!
Just found a solution though: paco. Paco keeps track of installed files if you run "make install" through it. Later you can easily remove the installed packages. Neat.
To build paco 2.0.7 from source in Ubuntu 9.04 you will need the libgtkmm-2.4-dev package as well (I installed it via Synaptic).
Example usage:
sudo paco -lp that-program-v1.1.3 "make install"
Some good cut-and-paste usage examples can also be found here