This item hasn't generated a massive amount of interet, but for anyone wondering about Sudan visas, we have now had our visas issued, taking only just over three weeks form start to finish.
The Ministry of Internal Affairs in Khartoum give the instruction to the embassy in London to issue the visa. As far as I can tell, they will do this if they are requested to do so by the Ministry of Tourism, who in turn will do this if they are presented with some letter of invitation / recommendation from within Sudan.
Therefore if you have a contact in Sudan, or failing that can get some Sudanese hotel / travel agent to recommend you to the Ministry of Tourism, you should be well on the way. We didn't use a visa agency - I suspect they would only be useful if you had no contact to invite you and they did. However, the agencies I spoke to had no such contacts, so didn't seem to have anything to offer.
Thanks to those who replied to my original question