Yah, if Anveo is truly having a systemic problem with E-911 setup, (and, they have that ridiculous limit on the number of 911 calls that can be made), their E-911 service isn't worth it.
There should be no requirement to verify via a phone bill. On Callcentric, for example, you just enter your street address, and then they verify it via their 911 service provider. I assume that provider uses some database of valid US street addresses (USPS or a third party). As long as you have a valid address, (vs. something fictitious or a typo), your 911 service should be enabled. And, when you travel or move, you can quickly change it online.