Useing Skype
 

Is Skype useful in learning Japanese (or for that matter learning any language)? If so, what's the best way to go about it?

For speaking. You can learn how a language works but have difficulty speaking it for various reasons, including having to quickly make grammarly accurate statements in your head and saying them without messing up. Something like Skype helps you do that with someone who knows you are learning and arebound to make mistakes, rather than going to a place that speaks the language and making a fool of yourself trying to speak to a native.

We get it all the time in the US, so much that some have gained the amazing talent of decoding what a foreigner is trying to say .. . I seriously doubt it's the same in every other place and culture in the world.

Yes.
1. Install it
2. Look for people who are in Japan
3. Message them and see if they want to do language exchange or something
4. Enjoy the fruits of labor

Sounds good, it's succinct and probably does what it says on the tin - I'll try it. Thank you.

One time while I lived in Japan, I had a Japanese girl message me out of nowhere. We did a language exchange, chatted, etc.

A few months later my friend introduced me to his new girlfriend—it was the girl!

They got married a couple years later and are still married. They met on Skype. :)

Though how does one go about messaging people from Japan through skype it not like you can send out an invitation to random Japanese person and expect a reply back from them. Though isn't throwing random invitations a bit rude and can be reported as spamming?

No, it's not. Back in 2005, it was happening all the time. I haven't used Skype in years, though.

You can search for user by country (used to do it by language, too, but I heard that wasn't possible anymore), then pick one and send a message like "want to do language exchange?" or something like that. If they ever get back and say yes, then organize a time to audio/video chat.