I got this msg too. The onboard computer takes in to account the miles and in-service time to calculate the factory recommended service interval. I think the upper limit for time is 2 yrs and miles is 20,000 (and/or a combination there of). Your car may be a late 04 build like mine is so according to the build date its about 2 yrs old. Mine went of at 8,500 and at that point the car had been in service for just about 2 yrs since it left the factory. So mine went off based on time factor...i think.
It's ironic that mine went of just a few weeks after i picked my CPO car so i was taken a back by it too.
I dont think the deals do any kind of reset in between.
Just have your dealer reset it and tell them you already had it serviced before the recommended interval.
Hope this helps.
