I have just done this route as far as Agadez in Niger as part of a convoy (hello other Hoggars who are also surfing here rather than working!). A bunch of us had CB, although with nothing like the kind of aerials you are talking about, and it was a godsend (tho our range was shocking). We didn't bother trying to get permits at any stage. The Tunisians didn't seem to care at all; the Algerians did search our cars when crossing the border but not thoroughly enough to find anything. We put the CBs back up about five miles after crossing and never took them down again (until we left Algeria, anyhow). Even though we had a government guide, were constantly stopping at police checkpoints - to the point that we had to camp several times by police stations, be warned that the police are a nightmare in Algeria, especially in the North - no one said a word about the CBs. True, one member of our party did manage to get arrested for spying in Tamanrasset, but bear in mind that this was because he pulled over to try and hear someone better on the radio, and happened to be opposite the main police station. When he still couldn't get reception he climbed on to the car and started waving the aerial about, leaving the armed police guards no other real choice but to pull him in. Even then they only held him for a few hours and when they let him go even gave the CB back to our guide.
Organising permits sounds like a nightmare - Algerian bureaucracy is staggering. Try simply stashing the kit on your person when going through the border: they only searched our cars, so this was a simple solution. Tho having said that there are some rumours around that they're getting tougher on electronic kit. Anyone out there actually tried to apply?