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.
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.......
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...