Because operations dealing with objects and their locations, such as collision detection and filtering nearby objects, are so heavily used in games, it is common practice to use one or more spatial data structures to describe your world. Some examples of these structures are grids, octrees, or the classic scene graph - a tree storing relative transformations in each edge. They are a perfect example of the tradeoff of using a little more memory to reduce algorithmic complexity.
These structures are useful because they allow you to exclude large numbers of objects from queries simply based on their approximate locations. For example, with an octree or a grid, you only need to be concerned with objects in the cells that intersect your query volume, and you can discard the objects in other cells, allowing you to prune lots of objects using only a few AABB checks.
However, I would refrain from having these structures actually store the objects themselves, and instead store pointers or references. If you do this, you can keep your objects tightly packed to improve iteration performance while allowing your scene graph to constantly adjust as your objects move around.
If you want to implement a messaging system, I would still use spatial data structures so that you can skip sending messages to objects that are too far away to care. In that case, you might implement a "message radius" and have the message dispatch system automatically make the query using, for example, an octree for objects within that radius, then send the message to the objects that the query returns. You'll save a lot of precious cycles that don't deserve to be wasted on sending messages to objects that don't need to receive them!