I've had other positive experiences with Gandi.net: They hooked one of their VPS servers up with a BGP feed so I could announce my AS there for testing a new Anycast service.