How does one deal with an uncooperative losing registrar? In this case, Network Solutions, which refuses to give up a domain name?

I have the AuthInfo code. I can receive email at all of the WHOIS contacts. The gaining registrar has sent me the authorization requests and I have accepted them, but Network Solutions persists in insisting, alternately depending on what CS rep I talk to:

1) "We never got the request from the gaining registrar."

2) "We don't allow transfers within 120 days of domain expiry."

3) "We don't have a procedure in place for transferring domains." [Yes, really, they told me this.]

What do I do?