Visual Voicemail doesn't require EDGE. I've been using visual voicemail quite a bit over the last couple of weeks, and have yet to see an EDGE connection (sadly).
It requires a cell connection, EITHER GPRS *OR* EDGE.
My VV has gone down a few times though, when out of cell range, which is a bit annoying as I get a red dot as if I've got a voicemail, and it's only saying that it's "currently unavailable". It soon comes back on though.