Thanks to davezaff for the idea.
Here is how I did it on my Focus Flash. You will probably need a way to edit the APNs.
1. Update to 7740
2. Update to 8107
3. Insert sim card into an AT&T Android LTE phone (I used skyrocket)
4. Go to att.com and switch plan to Data Pro 4g LTE plan. I had to call to switch since it wasn't working on the website.
5. Setup VVM on Android LTE phone (don't know if this is necessary, but this is what I did....make sure friend knows the VM password so they can re-add it when they put their sim card back in.
6.Insert sim card back into Windows Phone
7. Call Voicemail
8. Wait for VVM to show up on phone (mine showed up after calling voicemail).
9. If sync error, edit the APN as follows
APN settings (delete the internet_line APN)
Create a new APN
APN Name: pta
Profile Category: internet (always on)
Auth type: None
Proxy address: proxy.mobile.att.net
Proxy port: 80
I now have working VVM on AT&T with my Samsung Focus Flash. My internet tethering still works (applied the Interop unlock + tethering hack from XDA). I have not tested MMS since I did this, but the MMS APN was untouched.