You're not issuing the request correctly. Bing provides two methods: structured query and non-structured. You're mixing both.
Structured ("REST" like):
http://dev.virtualearth.net/REST/v1/Locations/CA/BC/V6G/Vancouver/Stanley%20Park%20Causeway?key=BingMapsKey
Non-structured (with query-string):
http://dev.virtualearth.net/REST/v1/Locations?locality=London&postalCode=SW1A&key=BingMapsKey
As specified on the reference page (http://msdn.microsoft.com/en-us/library/ff701714.aspx) a request similar to yours would need to be done like this:
http://dev.virtualearth.net/REST/v1/Locations?countryRegion={country}&adminDistrict={district}&locality={locality}&key={key}
Also, you should use the 2-letter ISO code. Thus, South-Africa would be "ZA".
Your complete request will be:
http://dev.virtualearth.net/REST/v1/Locations?countryRegion=za&adminDistrict=johannesburg&locality=melville&key=key
It returns something like this:
address: {
adminDistrict: "Gauteng",
adminDistrict2: "Johannesburg",
countryRegion: "South Africa",
formattedAddress: "Melville, South Africa",
locality: "Melville"
},
confidence: "High",
entityType: "Neighborhood",
geocodePoints: [{
type: "Point",
coordinates: [
-26.17535972595215,
28.008920669555664
],
calculationMethod: "Rooftop",
usageTypes: ["Display"]
}]