Unfortunately, Verizon modem/routers cannot be set up in true Bridge Mode, and setting up the Verizon router in DMZ mode will still result in NAT being implemented on the Verizon product.
So, when the AirPort Time Capsule is set up as a router providing DHCP and NAT service, the result is two products both delivering NAT service, hence the Double NAT error.
If you want to run the Time Capsule as a router on your network, then you will have to put up with the Double NAT error. Depending on how you have your network set up, you may or may not be able to get away with the Double NAT. Since this error can result in some unpredictable problems, it's not possible to say how, or if, your network might be affected by the Double NAT error.
You are correct in that Back to My Mac will not usually operate correctly with a Double NAT on the network
Things would be easier if you could consider running the Verizon router "as is" instead of DMZ mode, and then configure the Time Capsule in Bridge Mode. The Time Capsule will not act as a router in this type of setup, but it can still provide a wireless network feature. If the Verizon router supports UPnP or NAT/PMP, Back to My Mac might work. You'll have to try it out and see.