I've experienced Skype IMs in the 'Pending' status for an excessive duration on Android, too. (In addition to infinitely-pending messages with the little spinning circle in Skype for Windows). I've always shrugged it off as a quirk - until I missed a business meeting today and the other party didn't get my message. Needless to say, I'm looking for a real solution now.
In today's scenario, I'm using:
I sent the IM at about 2:30 PM. It's now about 6:30 PM and the message is still in the 'Pending' state.
What's worse, my client and I picked up the conversation via our Windows Skype clients just now, and new messages sent/received from Windows are showing up in my Android Skype conversation. The old message, however, is just stuck in the 'Pending' state.
I've restarted Skype on Android, and restarted Android, itself. Neither has jarred the old message loose.