I've just returned from Tunisia, flew in this time.
Having been told the following about the Austrians that to my knowledge are still in captivity, I can understand why they are a bit touchy on the subject about the south.
I was told, by a local friend of mine in Douz, that the above were turned back by the authorities twice, they even double-backed to a town in order to take a less well observed route. I was also told that at one point they phoned a friend because they were lost, and at this point, based on the gps reading, they were about 80km inside Algeria, the area from which they disappered. I don't know how much of this is based on fact but I was talking to this friend, of 3 years, and he offered the info, I had not even mentioned it to him.
If though, this is how it happened, one would assume that the Tunisian authorities are rather embarrased and trying hard not to let it happen again.
I'm not trying to provoke a dispute, just suggesting why permits are difficult without a guide.