auDA said it had audited domain names registered between 1 January 2007 and 28 February 2009.
Of the total 18,103 org.au domain names audited, auDA found that 4,113 - some 23 per cent - do not comply with the eligibility criteria.
The most common reasons for non-compliance included that it appeared to be registered to a commercial or apparently non-existent entity or individual person, or that the domain name registration details were "incomplete or unclear".
auDA chief Chris Disspain said a list of non-compliant domains had been provided to registrars, which would now be responsible for alerting customers and updating domain records.
"We're not saying these names are all bad regos," Disspain said.
"Often the records show up in the name of an individual rather than the not-for-profit organisation. In that case a correction just needs to be made to the record.
Disspain did admit that "a number should not have been registered".
Once the number of actually non-compliant registrations is known, auDA will examine whether the issue lies with one or more registrars, is system-based and whether or not it is systemic.
Registrars have until the end of June to update or delete non-compliant domains. Affected customers will receive notification directly from their registrar, auDA said.