I guess it could be the relay but it's strange that the car doesn't sputter at all. Even if the pump shuts off there should still be enough fuel pressure to make the car sputter for a second before shutting off.
The lights are still on in the dashboard so that's telling me that it isn't a loose ground, and if the lights stay on without dimming you're probably getting enough power for spark. Did the problem just start on its own, or did it happen after someone did work on the car? If the relay isn't expensive, you could give it a try just to rule out the fuel system. If it isn't the fuel system then it's weird that changing the fuel filter actually helped. Did you ever change the crank sensor?
I'm trying man, but I wish I could check your car out in person. It's hard to do this over the internet, but I'll keep giving help if I can. If you do take it to another shop, make sure you tell them everything that you changed and everything that you tried to make it easier for them to pinpoint. I'd really like to find out what's wrong with it.