Yeah, fuel pump sounds like a good guess.

I once had a hell of a time with the fuel pump on my GTI... the thing has two fuel pumps, one inside the tank and one outside. The mechanics replaced the outside fuel pump twice before actually trying to replace the inside one.

Funny thing is, the following week, they presented the exact solution (including the same make of car and the same symptoms) on Car Talk. Would have saved me a lot of trouble if they'd run that show three weeks earlier.

My symptoms were different than Rob's, though. I only had the problem when the fuel level was low (as the inner fuel pump only kicks in at low fuel levels).