My wifi signal at home is incredibly strong, so I doubt that is the issue.
I'm not talking about your WiFi signal - I'm talking about your ISP's backhaul speed from your router to the internet (particularly upload speed, which is usually slower.) What are your speeds? Did you try it at another location to rule out a firewall issue, or a blocked port?
I've never tried WiFi calling with a double NAT, but, if you have a router inside a router and it is not set to bridge mode, it could be that as well. Verizon doesn't say that's an issue, but that can cause problems. (This is another reason to try another location.)
Last thing - did you se up an emergency address when you turned on WiFi calling? That's required in order to have it work.