Talked to my buddy. He told me that your best bet would be to buy a prepaid SIM cards. The one(s) he'd recommend are MTC for Namibia and MTN for Zambia. However, he mentioned that you may have to register the MTN SIM with your passport if you are a foreigner.
He thinks that BeMobile should be the best option in Botswana. Another option is Orange, which is I quote: Decent, but not as good as BeMobile.
Let me know if you require further explanations on any of these and I'll try to get them for you.