FYI, I've had a LOT of Skype notification problems over the last nine months as I've posted about in other WPC Skype threads -- missing notifications, delayed notifications, Skype chat messages never making it to me, etc. These problems happened only on my phone and never with my Skype desktop app. I eventually realized I would reliably get phone notifications and chats from some of my contacts but not from others, so in talking to one of the more problematic Skype contacts I discovered that she was using an older version of Skype than I was. Once she updated to the newest version of Skype desktop, all those problems went away and notifications and chats are now consistently reliable.
So all that is just to say that some of the problems listed above could potentially have a lot to do with what Skype version your contacts are using.