The Sudanese visa is much easier to get if you are heading south. Current situation is that Sudanese consulate in Cairo will issue within 24 hours, but costs US$100 (possibly depending on nationality?) You should confirm if it is still necessary to have a letter of recommendation from your embassy. I have never heard of the 2 vehicle rule, but having met solo vehicles in Sudan with visas, I doubt this is enforced.
Visa heading north is much harder to get, and can take up to a month in Addis or Nairobi. Use a travel agent in Khartoum to get a letter of invitation - it makes it much easier. There are several posts on this site that list appropriate travel agents.