My GPS actually WORKS. Now I'm using its original cable, attached to a PC and then using hyperterminal for communication. Loads of NMEA-sentences are comming in.
The original cable is a USB to PS/2-jack converter. The GPS is a little black box with a cable with a PS/2-jack. That is, I don't believe the GPS is using the true PS/2-protocol - it's just using the same jack. If it were using the PS/2-protocol, my Basic Stamp wouldn't have been able to communicate with it using its standard Serial library. Also, In windows XP, the adapter is listed as a "USB-to-serial bridge".
All this doesn't solve my problem though - just puzzles me even more. This really sucks. I hadn't expected serial communication using an arduino to be so impossible.