Actually you can fix the Voice Mail Icon issue!!! The one that shows up in the top left corner, NOT the text mail issue.
Takes an OLD sprint phone and some time.
First, put your EVO back to a STOCK ROOTED ROM.
Get your old phone out of the junk drawer (HAS TO BE A NON ANDROID PHONE) and call Sprint. Have the OLD phone switched back onto your account (thus removing your EVO from your account).
Once the OLD phone is activated follow all the steps to activate your voice mail account.
Call your phone from a land line phone and leave yourself a message, then call your voice mail on your old phone and delete it. MAKE SURE THERE ARE NO OTHER MESSAGES IN YOUR YOUR VOICE MAIL ACCOUNT.
Now you can call Sprint back and reset up your EVO. Once your EVO is all set up your EVO will reprovision your VM account. Follow all the instructions to get your VM account setup again. This would be a good time to update all the radios, PRI and PRL and make sure you update your profile.
No go back into recovery and wipe all and either NAN Droid back to your old ROM or start fresh. If you Nandroid back to a ROM with the VM Icon on it, don't worry it will clear off.
Use Google Voice if you can from this point forward. I have flashed many AOSP ROMs since going through all these steps and I no longer have to STARE at the stupid VM Icon.