FIXED!!!!!!
Here's my "fix" and an idea as to why the voice-only network keeps showing up and why some people have gotten lucky enough to get rid of the message by flashing back and forth between stock and other random oddities....
I loaded a PRL modified to not use the "Extended Network" banner. I used the 51425m PRL created for Sprint phones activated on Verizon having ERI issues from this thread...
http://forum.ppcgeeks.com/showthread.php?t=50076
instructions are included in the thread on how to load the PRL manually on your phone and is very easy to do. The FAQ does say not to load this on a Verizon phone but trust me it's okay.
Note: If you use *228 or get pushed an updated PRL, "Extended Network" banner returns and so does the "Voice only network" pop up!
My theory is the ERI file is getting corrupted or replaced by the Custom ROMs out there. Somehow, with different flashing back and forth the ERI from the Stock ROMs is sticking for some users. By using this PRL, the "Extended Network" entry in the ERI is never accessed, thus no voice only popup. Data works too.
The downside to this fix is this PRL is 6 months old and does not include all the latest updates, especially for Alltel integrated areas. If you have service issues with it you can always call *228 option 2 and reload the current PRL. I may try or someone else can modify the current PRL and change the Roaming Indicator entries.
Please try loading the 51425m PRL and report back if you are getting the voice-only network pop-ups anymore. Once again, you can easily undo the fix by calling *228 option 2.