I think I found the answer serendipitously:
In Outlook, Tools:Options:Calendar Options:Free/Busy Options,
"Update free/busy information on the server every X minutes."
I had this set to 15 minutes.
Even though this should only affect the frequency with which the Outlook user's calendar is updated on the server, maybe it also affects how often the tokenized URL for accessing others' freebusy gets updated. When I set it to 1 minute and did a couple quick checks, things seemed to be working right.
By the way, this was after installing the Outlook hotfix mentioned at
Outlook 2007 improvements in the February 2009 cumulative update - Zimbra :: Wiki and at
Downloads: Outlook 2007 Update Boosts Performance and Responsiveness, so maybe that had something to do with it, but it's working anyway.