As far as HDD tests go, there's really quite a few levels of depth there - I mean, you can do tests, and you can do really stressing tests, that will take many many hours (or days) (I'm thinking of fsck since you mentioned linux).

It's not clear to me that the disk IS the problem, though, from what you've described. If you can't find any pattern at all for crashing, then in my non-professional opinion it is likely NOT the disk. Disk-related problems (be it the medium itself or the controller) tend to be quite repeatable and/or predictable (to some extent).
You can further isolate this if you for example just boot up a live cd and leave it running, or do stuff that does not write to the disk (or at least minimize disk access); and see if you still get those crashes. It's not a sure diagnostic unless you can manage to not access the hdd AT ALL, but it is a good hint, still.

Completely random stuff seems more likely to have to do with the RAM or the mobo (or even the CPU). Btw, another small experiment you might be able to make is the following: if you have more than 1 stick of ram, say 2 x 512M, take one out. Play with the laptop. If nothing happens, switch the sticks.
And even if you have just one stick, you can still do this by using another ram stick (from a friend, or buy one - doesn't have to be a 1G one, as cheap as you can find).

I guess you're getting my point here - process of elimination, like Lemur says. At least you'll know it's NOT the RAM. Or the hdd.

Can you convince the GS guys to change the mobo ?... (I don't even know if they do that, they might just end up giving you a new machine altogether).

Anyway, you can try these couple of things to narrow it down a bit.