Do these two sentences imply different meanings?
Our company is based in Melbourne, Australia.
Our company is located in Melbourne, Australia.
I would say so, yes.
It's subtle, though.
"based" implies that you are speaking of a head office even though the business may have sub-offices.
Some employee in the US might say: "Sony is based in Japan" [although they probably have offices in America]
"located" is simply specifying the location.
"The Sony head office is located in Japan"
"Based in" simply adds a bit of information about where the main office of a company is. Not always the case, but in many cases.
For how I understand it, based at Shirley means the center of operations are on Shirley, while located in Shirley could refer to one of the agencies of the business.