The system on my workstation was installed in 2008, December. Actually, I installed Debian AMD64 version over an i386 version on the same box, which was installed around 2003.
Debian ships tools that makes it easy to keep a clean system. For instance, debfoster allows to easily get rid of all no-longer necessary libraries and al: you just have to select the important pieces and it will remove any software that is not required by one of these. And apt-get, nowadays, just like deborphan used to, even warns you when some software is no longer required and provides you with the autoremove command line argument that do the job automatically.
(debfoster is, supposedly, deprecated, like apt-get is in favor of aptitude. Well, I like debfoster)
That being said, if I run
dpkg --list | grep ^r | nl | tail -n 1 on this box, after only one year, I get 617 lines about removed software I do not care about. Mostly, they were kept in the dpkg database because I (or me using the system) modified their conffiles. The following will clean this:
for package in `dpkg --list | grep ^r | cut -f 3 -d " "`; do dpkg --purge $package; done && debfoster