The Passkey Gen I system is VERY sensitive to things such as a dirty or wet ignition key, especially on the resistance chip on the key. Over the 15 years of that car, the key can build dirt up inside the the ignition and trip that starting problem. I highly doubt it is battery related, seems more like a coincidence.
Clean your key up, then try spraying a little contact cleaner on it, just enough to coat it lightly, and insert it in the ignition as if you were going to start the vehicle. Insert and remove it a few times, then repeat the whole process. Just don't drown the ignition in cleaner. Could try some canned compressed air as well to flush loose dirt out.
-DW