A domain name I want to use now shows as expired on 20-May-2004 by
"WhoIs" lookup on Network Solutions.  However, the Network Solutions
site will not let me register it?  What is the deal with acquiring a
recently expired domain name?  Is there a black-out period that must
lapse before it truly becomes available?  How is priority set for
selling the name to a new registrant.

NOTE: I don't want to pay a premium for an expired domain name, so I
have avoided directly contacting the former registrant/owner.

Network Solutions has, in the past, been accused of domain name hoarding:

http://www.wired.com/news/business/0,1367,37191,00.html

Most registrars permit the former registrant a grace period during
which they may pay the renewal fee and retain rights to the domain. 
Many registrars also offer a "back-order" service like SnapNames
(https://www.snapnames.com/backorder.sn) that permits you to enter an
order now to buy a domain when it expires and if the former registrant
does not act during the grace period then you may buy the domain for
the normal registration price (plus a fee to place an order through
"back order").

This is from the FAQ's at the SnapNames site:

Will I get my domain name on the date it expires? 
 When a domain name expires, it enters a "grace" period, during which
the current registrant can still renew. The "grace" period, over which
SnapNames has no control, is unregulated, but usually lasts from 30 to
45 days. It can be more or less depending on circumstances. Once that
period is over, the Registrar will release the name to the Registry.
The name then enters a 30 day Redemption Grace period. When that is
over, the registry processes the deletion, and approximately 5 days
later the domain name will become available. For more detail please
see the deletion cycle link on the SnapNames Product page.

See http://snapnames.custhelp.com/cgi-bin/snapnames.cfg/php/enduser/home.php