[Nefarious]

If you used real information for network solutions(Phone number does not matter) Call them, and tell them what happened. That's how I got mine back.
For outlook use one of the two security reset options, they can't be changed without the answer or the other email.

For skype you can steal it back if you know the email you used and five of the people on your contact list. Ask Anarchist, he is good at that.