In the previous post, I came to a conclusion that it was the wireless driver update which sent my wireless on a new vista laptop south. Today I finally got some time to debug it a bit further...
..And it turns out the previous conclusions were, well... not entirely correct. Ubuntu livecd certainly has very little to it from Vista - yet I got only 400kbps performance - while on the wired connection I got 4Mbps. Though, the connectivity appeared smoother, but maybe it is the more tolerant Linux TCP stack. So, the conclusion is that it is OS-independent, and how I got "good" performance in the first place is a mystery.
The access point I'm using was an almost 10 years old noname 802.11b. Given that all the neighbouring ones are 802.11g, I think mine is probably driving the neighbours' data rates down, so probably a good time to go and get something newer - and write how it looks after that.
Even though I did not try the G access point, this link might explain it - at least the symptoms match very well: http://ubuntuforums.org/archive/index.php/t-1032617.html
Now, how in the world that happened for both Vista and Linux - I don't know :-)
Indeed updating the driver from the linuxwireless seemed to alleviate the problem for linux at least.