With regard to the BGP &c., that only applies (AFAIK) to VPNs that terminate on the router. So, if one of your ISPs is friendly, they can help you out. Otherwise, that is not relevant to the current discussion. (Not that it isn't useful, mind you.)

One thing that I do not know about Highlander and embalmedlenin's situation is this: which endpoints are accessable to the internet, and do you control any other hosts that are on an open network? You're going to need at least one non-NAT'd box to route your communications. If it's one of the endpoints, then you establish the tunnel connection from the other box. If neither of the endpoints are directly accessible, you're going to need a 3rd, accessible host to maintain the tunnel. For instance:
Code:
                  +----------+  +-------------+  +----------+
endpoint1 -- 80 --|----------|->|<----------->|<-|----------|-- 443 -- endpoint2
                  | firewall |  | 3rd machine |  | firewall |
                  +----------+  +-------------+  +----------+
If this is the case, then I withdraw my earlier claim of "easy". I mean, it's still technically pretty easy, but it's definitely a PITA.