If you want to use all the 3ed rules for combat "with utter precision", I think you are going to need a map, whatever simple and rough it is. Certain things like cover, AoO because of movement, flanking, reach... are too hard to keep in mind.
But then who says that you HAVE to play the game with such a level of precision? Sometimes it's fun, other times it could be tedious. If the players agree that they don't bother too much about precision, and they trust the DM, it is perfetly acceptable to play without a map. DM's description can suffice in this case (although IMHO even showing a picture of the place is a great help), and the DM can make up some decision on the spot about cover etc.
You definitely need trust from the player, because sometimes you might rule (for example) that a move action isn't enough to close to the enemy, instead of being barely enough. Without a map, the DM decision is essentially random. However, if the player is able to accept this "randomness" just as he accepts any other randomness in the game, then the game works.
It happens often to me to run an encounter this way. In situations like when you're in a mostly featureless environment (e.g. an empty hall, a plain or desert, underwater/airborne) or when you're in a pseudo-random environment (a forest with trees in random positions), and you're fighting a single enemy, it is often not worth to keep track of everybody's positions. Most often the PC will gather around the enemy and attack from every directions, so it's enough to decide how many of them get the flanking benefit for example, but not necessarily to draw the positions exactly.
