Before I say anything else -- Is this causing problems? Because if its not causing problems, don't prematurely optimise it. I'm sorry if you already knew that, but it had to be said. If you don't know the old Knuth saying, I'll note it here for you.
Otherwise... Too much indirection is very often going to be a problem in real-time simulations. If you overarchitect things, this is the kind of wall you may well hit. You already know what the problem is; I guess it's time to make decisions about where it is really necessary to have that level of indirection. With entity systems, it is better to keep things very simple, as in terms of game logic this is "the metal" so to speak. Better to keep all that metal really close together.
The only other solution I can suggest is to use a much more efficient data structure... if that is possible in your case.
Why, if I may ask, is it a problem for your Behaviours (which are I think what I and I others would call entity components) to talk directly to one another?
I can suggest an article: Coding Cowboy -- Evolve Your Hieararchy. It should give you a bit of insight into how simple this can be, and has been in many games. In the article, the author is referring to the development of the early Tony Hawk games in particular.
EDIT: (In response to your 1st and 2nd comments) No, they wouldn't have to query the entity. That's the problem! Every individual EntityComponent has to have fixed references to other EntityComponents which it bears relevance to, or which bear relevance to it (depending on how you look at things). You problem is you're doing a lookup on every update. What I'm saying is you are meant to do this only once: You give each component a fixed reference to any component it depends on, from the time that these dependencies are injected, meaning, for example, that a pathfinding component is going to need to reference the spatial component; without it, it cannot know where it sits in space, and thus cannot pathfind. So you either inject all these components into your entity in the right order on entity creation (usually your entity factories will do this), or you build an intelligent system into your base entity class that rechecks all dependencies on every new component addition, and set fixed refs between them. But the fixed references are a necessity, otherwise you will face exactly the problem you are facing now -- no matter how you look at it, lookups have a cost and they do not belong at this point in your architecture, in any real-time game.
