Proper Architecture for Application-Level Collections

Given an application-wide collection of objects, and many unrelated classes that need frequent access to these objects, what is the best way to provide said access?

Example:

// Object A, stored in collections, used to do useful things
class A
{
  ...
public:
  QString property(const QString& propertyName) {return m_properties.value(propertyName);}

protected:
  QHash<QString,QString> m_properties;
}

// Collection class, contains methods to:
// - Access members of collections
// - Add/Remove members from collection
class GlobalCollection
{
public:
  // Accessors to collection/collection members
  static A* getAs() {return aHash;}
  static QHash<QString,A*> getAByKey(const QString& key) {return aHash.value(key);}
  static QList<A*> getAsMatchingCriteria(const QString& property, const QString& value)
  {
    QHash<A*> subsetOfA;

    foreach(A* pA, aHash.values())
    {
      if (pA->property(property) == value)
        subsetOfA << pA;
    }

    return subsetOfA;
  }

protected:
  QHash<QString,A*> aHash;
}

// Example client class that uses A's to do its job
class Client
{
public:
  // This is tied to a button click, and is executed during run-time at the user's whim
  void doSomethingNonTrivialWithAs()
  {
    // Get A* list based on criteria, e.g. "color" == "green"
    QList<A*> asWeCareAbout = ???;

    // Draw all the "green" A's in a circle holding hands
    foreach(A* pA, asWeCareAbout)
    {
      // Draw a graphical representation of pA
      // If pA has "shape" == "square", get a list of all the non-"green" "square" A's and draw them looking on jealously from the shadows
      // Else if pA has "shape" == "circle", draw the non-"green" "circles" cheering it on
    }
  }
}

Assumptions:

• Preference has been given to small, lightweight classes, so client objects are legion
• A client object could be several layers deep inside a "peer" of GlobalCollection, and intermediate layers have no dependency on A* or GlobalCollection
• This is currently implemented as a singleton

Design Requirements and Problems with Other Solutions:

• Dependency injection looks like an unreasonable burden on calling code (given the layering,) and sacrifices too much clarity for my liking
• I'm not opposed to a static class instead of a singleton, but that doesn't feel much better than a singleton
• Code that modifies the collection is isolated, so I'm not worried about that at this time
• The solution needs to promote thread-safety in GlobalCollection and within A's (given that multiple clients could end up working on the same A*.) This is currently being achieved with one mutex and overzealous locking, in large part because it is so difficult to manage access to the A's.
• I'm trying to iterate towards testability, and the current design makes nearly every test of a client require properly setting up the GlobalCollection first.
• In production code we have multiple GlobalCollections (for A, B, C, etc.,) so template solutions are welcome.

While I'm refactoring legacy code to do this, my main concern is designing the right architecture in the first place. This seems like a very common logical concept, but all the solutions I see fail to address some important aspect of using it for production or have a glaring flaw/tradeoff. Maybe I'm being too picky, but in my experience the right tool for the job has zero drawbacks in that context.