Skype has announced a new video messages features. Using the Android, iOS, or Mac app, you can send each other three-minute video message recordings. You cannot use this feature on Windows Phones yet. Windows Phone users can still see short visual notes, but they will have to follow a link within the chat section of the Skype client.
This new visual voicemail feature works online and offline. There is an option to download your messages to save them. The first 20 messages are free, but after that you will have to upgrade to Skype Premium for $5 per month.