[Ncgreasemonkey]

Alot of mazda 3's had the same problem you're talking about. If I had to guess without taking fuel hold pressure readings, I'd say it's gonna be your fuel pump. When a car is parked overnite, a certain amount of fuel is supposed to be held in the line by your fuel pump. (Or a check valve therein)
Your pump isn't doing that, and therefor, you're having to rebuild the pressure all over again in the mornings. It must be holding for a little while, which is why you can go in the store and come back out with no problems.
(It's fairly common for this to be the case.)