In my specific case, I found behavior trees to be awesome for fine-grained behaviors. For example, when one of the enemy avatars hears a suspicious noise, I want it to stop for a few milliseconds, turn around, raise it's weapon and look around for a couple of seconds. Using behavior trees makes that very easy. For higher-lever AI though, like deciding the most probable position of the player and doing a systematic sweep of a room (possibly with the aid of some allies), a simple hierarchical state machine turned out to get me the desired result much quicker and with less code.
I decided to use an influence map to allow the AI to track the player's position. Unfortunately, the enemies would often run around in circles because by the time they had investigated one corner of the room, another, already visited part of the room had filled back up. Tweaking the momentum and decay only got me so far, so I added an additional "channel" to the map to slow down the momentum for areas the AI had already visited. I'm pretty happy with how it turned out, the AI seems considerably less stupid now.
Here is a screenshot of my avatar being chased by an enemy:
Better quality: