My 2002 is doing the same thing. I took it to the dealer to have it looked at and they told me I was up in the night, and that it was working normally. When I got back in the vehicle to leave I noticed they tested it with the AC on MAX cold and Recirc. I know it stays cool then, but it used to freeze me out on fan speed 3 non-recirc.

I discovered a week later, just by accident, I turned the temp knob all the way to hot, then slowly back all the way to cold. The air coming out is much cooler than it was prior to me taking it in. And now keeps me cool inside without running it on recirc and full speed.

YMMV