Awake is only called on active gameobjects, maybe that's it?
In other service locators I think you often define the default instance registration at app start, in unity you could do this with https://docs.unity3d.com/ScriptReference/RuntimeInitializeOnLoadMethodAttribute.html
(caveat: I'd put a log in such methods since they'll always run at start, so there is a chance you might overlook removing them when you don't need them anymore and they interfering with your logic)
I made a service locator myself but i haven't used it much, it's a very simple implementation though
https://gist.github.com/FleshMobProductions/5588306c3d554154c65b6b9599eef8af
(later in my local code I added something to check some assemblies through reflection at game start and check if a type had an attribute on a static Instance property of its class, and if so add it to the provider automatically. I think i disabled that behaviour for now though and would register instances manually if i had to use it)
Big O notation i feel like doesn't matter much here as your input size will likely not be a lot.
the architectural benefits could be nice though,
if you combine that with service instances being returned as interfaces, you could also do something like: in a context of tests you set up different instances to be returned than in the production code.
GameObject.Find("blah") is a bit heavy when it comes to thousands of gameobjects
true, and it can be really nice to just handle stuff in code, over lets say inspector assignments.
the simplest approach I had to that was just to have a class that holds a static instance of a given object https://gist.github.com/FleshMobProductions/a73b4c49db3c02925346a0922fd61e40