That hostname doesn't appear to actually be registered (it doesn't show up as a glue record with the root servers, anyway). I do see a record for ns1 / ns2, which is also where this domain is pointing to, so I assume that's what you're talking about.
In any event, you would be able to do this, but you would need to modify the host (ie nameserver) registration entry with network solutions / verisign in order for it to work properly (we can't do this - you'd have to do it).
The simplest thing would be for us to set things up on our side, and for you to then modify the host entry. If you can get your old provider to play along, you could get them to modify their records to point to the correct IP addresses in the couple of days before the glue records updated.
I'm not sure if there's a fee for this service with dedicated machines... there may be a setup fee associated with this service, and the two unique IPs that will be required may come out of however many unique IPs your plan is allocated.
In any event, sales or support may be a better way to get an answer to this question -- I'm the person who would most likely deal with it, so you can ask them to pass the question along to me.