Prueba como te digo con otro cable usb, sigue los pasos que pone en el manual para instalar la impresora (ya que hay algunas que tienen que estar enchufadas y otras que no). Si despues de esto no te funciona....
Cuando desinstalas todo lo de lexmark reinicias el pc ?? Prueba a quitar todo el software y drivers y reinicia, despues pincha la impresora por usb al pc a ver si te reconoce algo, si ves que no prueba todos los usb del pc a ver si va a ser ese el problema...