Napster only seems to carry domestic releases (no Heater Nova - Storm for example). They do carry some out-of-print albums released in the US though.
Napster Premium is actually a decent service for what they do carry though, since you can play full tracks from as many CDs as you want for the flat $10/month, you just pay extra to burn or copy to a portable. I have it installed to my music server so I can alternate between previewing CDs and listening to ones I already own. 128 kbps WMA sounds much better than 128 kbps MP3 and FM radio.
allofmp3 = warez, just use usenet if you are going to infringe.