A properly packaged application shouldn't leave anything behind, but you most likely will end up with at least some left over config files, directories, etc.

Not much can be done about that aside from contacting the developer and asking them to make a nice script to remove everything generated by the program after an uninstall.

Well, a normally well-done package will only leave config files.
And this is good, it takes a few hundred bytes and in case you reinstall the application, you still have your settings.

It's no fun when you remove an app, but the config file stays, and then a year later when you install a newer version of the app, it craps out because of old junk in the config.

I've got years of bit-rot on a few machines, it's amazing anything works on them at all

Fortunately I'm a big fat geek so I can usually track down the evil..

On real debian, if the config file has changed (either because you modified it or because the default one shipped has changed) then it will ask you
Keep your config file
Take the new default one and make a backup of yours
Show the diff

But on the IT, I've not been able to completly erase a config file.
apt-get --purge remove <package> does not work.

I've really never had a problem with config files. Usually I will show the diff and then use the maintainer one, then use tkdiff to merge back my settings in the old config file.

Even if it's not straightforward, I don't see how they could have done something better.

I was thinking more of config files, or other junk, generated after running the program (not originally part of the .deb)

It's generally not a huge problem, but it would still be neat to have the postrm scripts ask about removing left overs created by the executables, of course I don't expect most maintainers to ever actually implement this. I would personally never bother since I'm lazy