It sounds like he's been flagged dead. I've never known it happen to anyone but your character, but it's completely possible. I'm guessing he hasn't actually died, hence why he still appears as if he's following you from place to place, but his scripting has essentially stopped, and you're searching him when you click on him.
Have you reloaded during combat at all? Have you noticed it happening after a certain combat encounter? Have you tried to actually kill Sulik since he's been flagged?
If he has been flagged dead there's something you can do with your save file and a hex editor. Truth is I know almost nothing about the code and what values and figures interpret into what function. You'd know what I meant if you had the hex editor
I used it to unflag my character when he was flagged dead, it's an annoying bug.
My suggestion would be to goto the No Mutants Allowed forums and post your query there, and hopefully someone who has some experience with the hex editor will know what code to alter, you'll be able to send them your save game file and they'll be able to do it for you, no hassle. Someone there may even be able to tell you what's wrong, as I might be incorrect in my diagnosis.
Note that you cannot register at NMA with a hotmail account. A gmail account or something similar will suffice.