I'm working with a client who is in the same boat. Network solutions makes it extremely painful to try to transfer your domain to another registrar if you aren't listed as the main contact on the account. In my client's case, both the technical contact and the main contact aren't with the company anymore, so we're having to fill out paper work and fax it back to them to get the issue resolved.
For what it's worth, I have had good luck with other companies with either threatening to complain to the BBB or actually complaining if they take the threat lightly. Many companies will look past their standard policies in order to satisfy a complaint to the BBB.