Well, as you said, he is nearly impossible to destroy by a conventional army. So try non-conventional means. Here are a few :
- Black bow of Beowulf -> Feebleminded sphynx that can't teleport anymore. Takes care of at least one problem
- Ethereal Crossbow -> instant death (well, if it hits and passes MR)
- There's also an Axe that forces a MR check to avoid Death.
- Mind Duel. A teleporting Sphynx must have astral, so he is vulnerable.
- 400 Ulmish Arbalest on "fire and flee". Should at least net you an affliction or two
Add Wind Aim and flaming arrows if possible. Curse him beforehand for maximum effect. Watch the afflictions pile up. Can also be used with heavy infantry or cavalry...
- Target and destroy the enemies labs. Without labs, the sphynx can't get the gems he needs to teleport.
- Burden of Time, pretenders are not immune
- Decay, disease, blindness...
- An good ambush. The point is to make the Sphynx teleport and attack inside your territory, and hold 40 turns (or is it 50 ? ). Use paralyse, fatigue inducing weapons, or endless supplies of imps, whatever you can come with to keep him occupied (and you alive) thses 40 turns. Then the attacker (him) routs, finds he has nowhere to retreat to, and die.
I am sure there are other ways as well