That happens sometimes rarely, but if you disconnect and reconnect your internet, you'll see them online (that is if they are online).
EDIT: If you have met them on on PSS but not as friends, rather acquaintances, then they will not be shown as friends, rather acquaintances. In such cases you have to fulfil the usual norms to have them as friends i.e. accepting the friend message after 1 trade/battle, without DC (In case of him being an acquaintance)
Source: Experience, it has happened two or three odd times
Hope I helpd!