The main requirement is the MTU size to support SDA operation. The core fabric recommends ~9000 bytes, but realistically the size is to enable VXLAN support, so potentially doable with 1600 bytes. Looking at the VXLAN specification it is less than that, but not sure on any other overheads. I'll be confirming this soon with some work I'm doing as 1600 is a limitation of some of the intermediate nodes.
You don't need to have a Border at the remote site unless you want to break out locally, but you can if you want. The other option is multiple fabrics, but then you lose the portability benefits.
The challenge you'd have though is your provider. If it's a dedicated managed service then you may be able to get it sorted out (for a price). If you're talking about the Internet, then not sure how far you'd get with that. You can try some ping tests from HQ to Branch with DF bit set and see how you go, but that is not going to guarantee anything when contention kicks in...
