Nonono... Im not talking about the computer's microphone. xD
I just tried to avoid people suggesting to use it.
It occurs on my N900.
Recording with the Recording app works fine and noise-free, so I suspect Skype's servers or maybe the client itself.