I bought a video-projector with a 800x600 native 4:3 resolution, so
when I do 16:9 on it, the resolution is reduced to 800x450. I was
wondering if there was add-on lenses that could "compress" the picture
to get a 16:9 aspect-ratio and keep my 800x600 resolution at the same
time. My projector is an Infocus X1, and I doubt add-on lenses exist
for this particular model, so a generic one that "stands" in front of
the projector is what I had in mind.

Yes, such lenses do exist, but one will set you back at least $500,
with some models costing $1,000 or more.

The three big names are:

ISCO "16:9 Video Attachment"
Widens image horizontally, so the projected image will be wider than
you have now.
http://www.iscooptic.de/english/products/video169.php

Panamorph
Squeezes image vertically, so the projected image will be the same
size as a letterbox presentation currently is, but with higher
resolution.
http://www.bigscreendirect.com/PSOSeries.htm

Prismasonic
A relative newcome to the market. More affordable than the other two,
but may be less optically "perfect". With optics, you frequently get
what you pay for. They have models that both stretch and squeeze.
http://www.prismasonic.com

The premier source for information about almost anything related to
home theater are the AV Science forums, at:
http://www.avsforum.com

Searching there for any of these brand names, or the term "anamorphic
lens" will return a plethora of useful discussions about these lenses
and their use.