Same for me, except I use d20 Pro for my VTT. Even if all we're doing is talking to NPC's, I have some map of the area up. IME, it helps everyone visualize what's going on and keeps folks focused.
2E - 10% of the time (although we wanted to use them more)
3E - 100% of the time (tried to go without it twice and found it impossible)
4E - 100% of the time
We now use minis and battlemats for every game we play. Star Wars (all incarnations), Mutants and Masterminds, ShadowRun, and so on.
I put sometimes, most combat is handled without it, only serious combat is handled with and even then it is simply a quick way to figure out rules stuff, ie: we don't actually describe the game as it unfolds on the battlemat.