Related questions:
To make a research plan for this family, I would start by making a list of the source records you have found so far. Make a timeline of the events, using paper, a spreadsheet, a table, index cards -- whatever tool suits your workflow.
For each record type you already have, review each one to make sure you understand what agency created the record, what purpose the record was created, and so on.
After you have done your review, do general research on Australian law. What is required now for contemporary changes of name? When did those laws come into being? Can you follow the breadcrumbs from what is found in the current statutes back to the period you are researching?
To generate a list of possible records to search in --
- Look for books and research guides on doing research in Australia that might give you clues about record groups that you might have missed.
- Consult guides such as Mark D. Herber's Ancestral Trails in case there might be records in Great Britain about your people as well as in Australia
- Look for research strategies in the FamilySearch Wiki -- start with the upper-level article on Australia
When looking for records:
- Don't restrict yourself to looking for records on the standard 'big-box' websites devoted to genealogy. Look for finding aids first.
- Use guides like the Record Finder in the FamilySearch Wiki
- Check Archives at all levels -- National, State, and Local
- Check Libraries at all levels -- National, State, and Local for both finding aids and special collections / manuscript collections (and what in the USA are called 'vertical files' -- collections of loose items of interest)
- Look for holdings at genealogical societies and historical societies at all levels -- National, State, and Local
- When searching big websites like Ancestry, Findmypast, MyHeritage, RootsWeb, etc. consult all levels of jurisdictions that might have records
- If you don't already know how, learn how to do a place search in the FamilySearch catalog
- Search using keyword searches as well as using search boxes specifically dedicated to names
- Don't neglect newspaper research -- you have Trove Australia which is a superb resource
- Search in genealogical publications for other researchers who have documented similar kinds of name changes. Look carefully at their source citations and bibliography. What sources were they able to find? How did they correlate their data?
- Search for bloggers, magazine articles and books where people are studying the same locality to see if you can pick up clues.
To solve this problem, you'll have to step back from the search for a list of individual records you can look through and consider the big picture -- what was required when people changed their names. There may not have been a legal requirement for a notice when people changed their names -- or if there were, the notice may be buried in a local court minute book, or the legal notices in a local newspaper.
