There are several ways to send a message on someone elses skype. Much computer science-y stuff ahead;
1: They got your password, put it on a list, the list is accessed by a bot that puts out the desired spam to all contacts or something similar. This is the most likely. I recommend getting
http://keepass.info/ put a very strong master password that you can remember then just
generate all your passwords and store them there.
2: A program is listening to the same port as Skype is, fishing the handshakes for the keys to decrypt/encrypt messages and then simply sends its own packages down the same open line using skypes
protocol. The good old msn viruses did this, if you do have one of these they'll be found in your process list or services.
3: Code injection, this is what nwnx does to nwserver. It rewrites machine code instructions so that they do something else or jump (or call) another section of the program or custom code that you've loaded into memory. If someone has decompiled and reverse engineered parts of skype then it'd be trivial to create a program that injects codes into it that forces it send the desired spam. However your anti-virus would most likely detect and some programs has counter measures against this by checksumming their own loaded program.
Code injections can be modifications to the .exe which means it'd be undone if the .exe file was replaced. Code injections that happens on running processes needs another process to do it as an example NWNX.exe is starts and injects code into nwserver.exe. The functions required to inject code also requires elevated permissions.