I know you said you tried it with various States, etc. and it still didn't work.
If you have the cspeech.dat files
in the NA map folder (which it appears you do) AND you have the current map for which it works (7.10 or higher), which it appears you have AND you have the support file, which it appears you have, then VR should work.
Check these out:
1. Make sure the support_asr.dat file is NOT really support_asr.dat.txt. In Control Panel, Folder Options, View, Advanced, make sure 'hide extensions for known file types' is UNCHECKED
2. If the file is ok, have you tried a pin reset? Does that help?
3. When you are attempting to get VR to work, are you selecting the Spoken Dialog option for VR; if not, try that.
4, If you have gotten this far, try this: completely manually, go through the Navigate to-->street and address and select your state, a city in your state and a street and number. Once the route is calculated (you cal always delete it later -- Clear Recent Destinations or Clear Route), now try to use the VR options to go through the process. Does that help?
5. Gotten to here? Download and run the Clear Flash tool
from this link. Run it 3 times. (don't worry that it doesn't mention the 720 model)
Any better?