You can hire an Avis car from Maputo, but you can't do a one-way drop off from Maputo to JNB or visa-versa. That suggests to me that they have two separate fleets. Certainly the larger companies have no issue with cars going between South Africa, Lesotho and eSwatini (Swaizland) provided you request all the documentation before you pick up. There may be an additional charge but I think most people find it insignificant. Mozambique might be the issue.

4x4 companies are very used to their vehicles being taken out of SA, at a price. If you don't have any luck with the major car companies, try the 4x4 specialists.