I'm sorry to hear you're not out of the woods yet. The positive take on all this is that it seems most likely the problem has to do with the cartridge, given the elimination exercise you've been engaged in. That should help Lexmark pinpoint the cause of the problem and, most importantly, come up with a fix. I would appreciate it if you could let us know how things develop.
