Hi, I own a small computer repair company and have the exact same problem and was able to fix it. After many many hours of trial and error...here's what you need to do.
This regards when Vista says that your lexmark printer is always offline
Got:
ftp://ftp.lexmark.com/driver/inkjet_drivers/Cleanup/ (copy and paste to browser)
and download the file that corresponds to the SERIES of your printer.
After you have it downloaded...make sure you have the newest driver from Lexmark's website for your printer.
1) Unplug the printer from the USB port
2) go into control panel > printers
3) delete all occurences of the lexmark printer
NOTE: they may not disappear until you reboot
4) reboot
5) use the cleanup utility you downloaded from lexmark(right-click it and run as administrator)
6) you should be prompted to reboot after the cleanup utility runs...if not reboot now)
7) now that you have booted back up...right-click the driver and run as administrator

you might notice that it stops mid-install...if so look for a small box in the background notifying you to reboot after you are done. click okay on that box and let the install proceed.
9) follow all the prompts and eventually you can click "exit" and then "finish"
10) at this point I chose to do a test print which did work, but then subsequent prints did not work until I rebooted...so REBOOT
11) you should be back in business with everything working properly.
12) call lexmark and tell them they suck, because their solution is to sell you a new printer.
