I'm not in the bay area.
Given your constraints, I wonder if what you actually want is one switch for each upstream, and a gigabit link from each of your physical Xen servers to each switch that goes to an upstream. If your switches have to route at all, they can each have a default route to the one respective upstream connected to that switch. Then, have a VM on each physical Xen server with full routing tables to control how the outbound packets from all the VMs on that physical host get routed. And hopefully your switches can deal with a /32 route for each VM or something, if they just have a route per VM plus a default route to the one ISP they're connected to.
There's also the variant where you have a /24 block (or something) which has one IP address which is your ISP's router, and then one IP address per physical Xen server, and if your ISP is willing to take individual /32 announcements to your servers (I think this is technically feasible, but may require more mental flexibility than some ISPs have; on the other hand, I think you're talking Cogent, and mentioned that Cogent is willing to peer directly with your customers, which may imply that you're dealing with a flexible ISP), you can have the ISP do the layer 3 routing to the right physical host for traffic going to each VM. (The idea is that the ISP would not propagate the /32s to their peers; you'd separately send them a broader announcement that they could pass along to their peers.)
One other issue in this scheme is that if a single gigabit link between one physical Xen host and the switch going to one ISP breaks, inbound traffic that happens to come to the ISP attached to the switch with the broken link ought to have some mechanism to find its way over to the other switch for the one physical Xen host that has the broken link. I think there are ways that OSPF and or iBGP with the non-default next-hop-self setting can be made to do this.