My 05 shifts immediately into OD regardless of temp. But I wanted to mention that there are some other vehicles that do require a certain fluid temp before they will allow OD. When I worked at Nissan in the 80's and early 90's we would have a run of customers every Winter complaining about their cars not shifting into OD until they drove it a while, (variable depending on ambient temp). And they would always claim it never did that before, but they were wrong. In summer it was never an issue since it reached the threshold so quickly. According to Nissan the reason they gave for it was to help the engine heat up more quickly, primarily to make the heater get hot sooner. Not really any mechanical reason for it.first of all, the OD is not related to temperature, the trans should go into OD at the right speed & engine load regardless of if its -10f or 100f. so its not related to temps of the engine or trans/fluid.
the fluid is not lifetime, toyota recommends change at 100k miles or 60k if towed or abused, however, at 110k miles its should still be ok depending on its history. based on the symptoms you describe i dont think a fluid change will fix the OD issue unless its low, sounds like its solenoid/sensor related or possibly shifter/cable adjustment issues. best is to have a mechanic or trans shop look at it & test & diagnose further. also check for any codes that may be strored. but a fluid exchange is due so it cant hurt to try that first.