EDS was awarded a nine-year contract to overhaul the state's entire IT infrastructure in 1995. The contract was worth an estimated £250m.
In a report published last week, the Australian auditor-general, Ken MacPherson, found EDS guilty of charging the government above market rates.
EDS denied the allegations, arguing that the prices arrived at were the result of a systematic price review, guaranteeing mutual fairness.
In addition to forcing EDS to pay money back, the South Australian government has forced the IT services firm to adjust its prices for the remaining six years of the contract.
The outsourcer has now been accused of overcharging the Australian tax office for computer peripherals.