`checkinstall` is definitely the way to go but if you didn't use it to install the program, you can't use it to remove it can you
What you need to do is, as Technoslave said, `rm` the program files. This can sometimes be easy if they were installed in /usr/local/ and all the files are easily identifiable. Sometimes, though, an install strews files all over the place: libs, binaries, manpages, etc. That can be a hard thing to remove completely.
Usually, though, unless you have a conflict with something you can leave an app where it is and just stop using it. If you are getting a conflict with another installer then delete the files it's conflicting with.
Yes this will clutter your system, which is why you should start with `checkinstall` from now on
PS Big apps like OpenOffice tend to install themselves in a distinct folder that you can just rm.