I located the culprit.
It was something related to timing (as I expected), though it was of a rather unexpected cause..
Found the problem thanks to this topic: http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1268626974
Turns out that the read() method of NewSoftSerial also needs a tiny delay in order to get the actual value.
Still a bit annoyed that this isn't documented, but that'll pass.
Now the whole world of the arduino will open for me =)
Thank you to anybody who spent time trying to solve my conundrum.