PCM Relearn?

Before going out of town for 1 week I removed the connection to the negative terminal of the battery of my 96 Cadillac Seville SLS, so as to prevent power drainage. When I came back, I connected the battery again and noticed that the car was hard to start (took a couple of cranks before it started). After that first start everything was fine. However, the next day I noticed the same problem (hard to start) in the morning when I first try to start it. Took it to a mechanic and he said the battery was not holding the charge so I had it replaced. The next morning... Same problem! So I took it again to the mechanic and he said the battery disconnection may have affected the computer as it gave a P0603 code; so he reset the code. The next morning... Same problem. It seems that the problem appears only in the morning during the first start of the day but after the first start everything is fine!

Last Sunday night I parked the car in the mechanic's shop parking lot so that he could start it first thing in the morning and see what I am talking about. Monday morning came and when the mechanic tried to start it, it miraculously started at the frist crank (although it was around 3 seconds delayed). Something it hasn't done since the old battery was disconnected! The next morning, when I started the car, again, it started at the first crank but around 3 seconds delayed. This morning, when I started it. Its as if it never had any problems as it started normally. Did the PCM just relearn? (Mechanic told me before that there seems to be no problem with the FPR as I suggested to my by someone else.)