To me the solution is too simple. Every police and fire department has a phone line in their dispatch room called "the non emergency number." All you have to do with VoIP is program that number into speed dial. Problem solved.
Now, if you're an VoIP provider when you're signing up the customer, once you have the Zipcode how hard would it be to ask if the user would like their emergency services provider's number loaded in to their speed dial, as you guessed it. 911.
Now to take it a step further, when the IP address of the telephone adapter changes the service could likely be set up to "call you" with a message that says something like "we see you have relocated your telephone adapter. For safety purposes we can update your 911 to dial the local emergency number. Just enter the zipcode you are currently in."
Too simple....now I know some privacy advocates will get all over me on this, but for those who need to feel safe and secure, it may be a more easy to implement solution than the ones I'm seeing deployed.