Go and get some good webcam (I use the Microsoft LifeChat NX-6000), navigate to the Skype user settings
open config.xml and follow the instruction by Phillip Torrone, seeking for the <Video> tag. I am using Skype version 18.104.22.168 and the configuration file looks quite different now. However, adding the <CaptureWidth> and <CaptureHeight> tag works fine as well with this version since it was especially introduced with version 3.6. At the end your configuration file should look similar to this one.
I re-started Skype and it looks like the other side can see me in 640×480 now.