Is there a listing anywhere that gets updated regularly that shows free or recently released domain names from Network Solutions?

Ouch..... I don't like your chances, such are NetSol's wonderful policies of keeping good domain names.....

You could always keep an eye on http://www.domainmailings.com and see what names come up...

You might already knew this: whois.net and some other similar ones.