Hm... Did he appear in your empire directly? If not he maybe appeared in a Muslim realm that was later conquered, ended up in your empire and got converted before starting his invasion?
Or maybe you had a Muslim vassal for a short while, then you converted him and he converted Sabuktigin?
I went back and checked a save from just before he appeared. It does appear to have been a conversion. Sabuktigin appeared in the court of the Count of Feranga. Not my direct vassal, but the vassal of my duke level vassal of Samarkand. At the time, the province was Zoroastrian, but the count was Sunni. I just didn't notice because he wasn't my direct vassal. The count was revolting against the duke. At the start of my save, there is a stack of about 11K on the count's land ready to siege him down. Sabuktigin hadn't spawned yet. Letting it play out from there, the count lasts about three months before his lands are all assaulted and he surrenders. This time, Sabuktigin did not appear there or anywhere else. The count was imprisoned and had his title revoked.
In a save approximately three years after Sabuktigin appeared, the count is zoroastrian and Sabuktigin is in his court as a zoroastrian. So, my guess would be that in the original playthrough, Sabuktigin appeared while that count was revolting. Either during that revolt or shortly thereafter the count must have converted and Sabuktigin converted along with him.