I am having the same issue with an x4875. I have tried reinstalling the printer several times with the CD and with the driver
from the Lexmark website. It also does not matter if the printer is connected via USB or WiFi. I also tried creating a TCP/IP port but it did not print at all (this may have been after the spooler was already blown and without doing a complete uninstall/reinstall). There is no uninstall utility available from Lexmark. In fact the driver I downloaded was from the x4850 page since there was none listed for Vista for the x4875.
Also of note, I have checked each time to see if the spooler was not running and each time it is still running. Stopping and restarting it does not help. It is basically necessary to completely reinstall the printer to get a single page.