That sounds odd. Are you seeing any error message or are the songs just grayed out? If they are grayed out, keep in mind that due to licensing agreements with the labels, content varies from region to region. Sometimes even, agreements can’t be reached with the artist or label, or a change may happen in music ownership. If you can't find an artist/song you’re looking for, they may appear (or reappear) soon.
In the meantime, feel free to contact the artist or their label to ask when they plan to be on Spotify.