I see that you've seen the recent thread on this.
http://www.toyotanation.com/forum/t237995.html
I just have my original cure (i.e. ignore the problem) and wild speculation.
Maybe the engine has sludge. I'm not sure why this would cause the problem, but if the engine is not breathing right, who knows what may happen. There is a product called auto-rx which may help.
I've also read that some people have installed a "fake O2 sensor" in these cars. That may help, but may also cause other issues. You'll need to search this forum (or the other Avalon forums) to find out about the fake O2 sensor.