Ha. I have not actually been back to Oz for 6 years now.. and apparently things have changed a lot.
I didn't know there was one in Horsham, or Renmark for that matter.
I was originally referring to the Melbourne->Mildura drive, but obviously I need to update my facts. Sorry 'bout that.
Eyeballing Macca's Australian website [1], I'd say that the furthest point would be equidistant from Kalgoorlie, Broome and Alice Springs. That's pretty close to the north-eastern corner of the Gibson Desert Nature Reserve [2], 800km from the nearest McDonalds.