Moral of the story: All but 1 Harmonix-authored track is available on PS3. A subset of the Rock Band Network content is ported by Harmonix to the PS3 platform each week (roughly 5 songs per week), usually the stuff that will sell well.
If you're talking specifically of the song count under "Rock Band" on the site, there are several categories of songs you can have in Rock Band 3 that don't appear in the store.
* Rock Band 3's 83 song setlist is included on the list - obviously because they're not DLC.
* Exports are not in the store unless they've been re-released as DLC. This includes many songs from Rock Band Blitz, and most of the LEGO Rock Band setlist, all of AC/DC Track Pack, as well as the vast majority of Rock Band 1 and 2.
* A small number of tracks have never appeared in the store, including the 20 songs that came as the free bonus pack for new purchased copies Rock Band 2.
* Mama I'm Coming Home and Bark At the Moon by Ozzy Osbourne can only be purchased as part of the Ozzy Osbourne pack, so do not appear in the store as separate songs.
As someone who has all but 13 officially released tracks on PS3, with a total setlist over 2,700, trust me when I say you'll find plenty to work with in the store. If you really absolutely must know what songs are and aren't available in one list, the wikipedia article on
Rock Band Network songs is kept relatively up to date.