How are these alternative IPs set up? I've done a handful of multi-IP hosting on a single NIC in Linux with no problem, but I've had full control. The IPs are real, I just bind several of them to a single NIC, then fire up AOLservers to listen on that IP, and all works hunky -dory.
To some extent, you may be the victim of getting service rather than a bare box. At least with a bare box, you know you can configure it right (even if it takes our help!) Don't get me wrong, folks like Verio ought to be able to deliver meaningful service, but you're already seeing one snafu on their part. They wouldn't charge you less for less service, so they probably don't have any real motivation to help you fix your problems...
