We use mage night pieces, minis, counters and sometimes dice and also 20 plastic zombies (from a bag of 100) that I've taken the time to number if the party is facing fairly similiar mooks.
Before 3rd edition (and I've been playing for almost 20 years now) we probably tracked combat about 10 times ever. That was for extremely weird terrain and combats that had who was where be an important story driving issue.
With 3rd edition you now have feats and skills that affect combat and how you move and who is near you while you are fighting, shooting, casting, whatever...
It's not fair to somebody who passed up taking alertness, stealthy and nimble fingers for dodge, mobility, and combat reflexes if they don't ever get to use their skills because where they are in battle is probably going to get glossed over more often than not. That's why we use a map so we don't screw over the people who took combat feats other than rapid shot and power attack.
Also, if I maxed out tumble, I'd be pretty upset if I never got to use tumble because where people are on the battle field isn't clear and the battle devolves into one-on-one combats.
With all the options the feats and skills in 3.X provide not having a map limits the options worth taking.
There's plenty in the game I can still use my imagination for but I think it does the players a disservice not to have a battle map or at least some hex paper on a cork board with some pushpins...