Skype contacts couldn't hear her. We had recently upgraded her computer to Windows 7 x64 so I figured it must be a bad setting in the recording device. So enable microphone boost, turn up the recording volume, make sure the microphone actually works, make sure the latest version of Skype (4.2 as of this writing) is installed, it all looked good, but her contacts still couldn't hear her.
Skype has a great built-in way to test calls by simply adding or calling the user "echo123". I called echo123 from her computer, and all I got was silence from my side. I tried yelling into the microphone and turned out I could hear myself in the distance. So the microphone actually worked, but it was just really really soft.
The strange thing is, all other recording applications worked fine, such Live Messenger or Google Chat, so it must be a Skype thing. As usual, Google searches only turned up recommendations that I've already tried, and it was quite obvious that the people giving "solutions" never experienced these problems themselves. However, I did learn that I could change the default recording format, but that didn't work for me either.
It turned out that the motherboard (ASUS M2NPV-VM) has a SoundMAX AD1986A chipset and Windows 7 automatically installed drivers for it, but Skype has compatibility problems with the standard drivers. After installing this driver on the ASUS FTP site everything worked as expected... but since I had mic boost turned all the way up and recording volume at max, I nearly blew my ears out.