The product in the link you've provided works on 802.11 technology. There needs to be a useable (and supposedly, legally open) WiFi cloud for this product to work. T-Mobile, among others, has such service through different places (Starbucks is one).
Totally different than EVDO. EVDO works on CDMA cellular network.
Currently, it's quite fair to say that the availability of EVDO is much higher than WiFi. So if you want "always-on" internet, EVDO is probably the better bet. As for the question you have on your moving plan, have you called Verizon's customer service and asked them?
Also check other alternatives; ClearWire probably?