I am running Outlook 2013 on an Exchange 2007 sp3 Server. When I change my Out of Office (OOF) reply in Outlook it looks all fine (no Error messages) then when I look at OWA it shows that same OOF message when I go to change it (they sync back an forth).

The problem is that it no OOF message is actually sent... I tested it with other email addresses both external and internal and nothing comes back to me. There are other users having the same issue only they look like their OOF should be turned off but it is still sending.

Autodiscover looks fine, we reset the CAS servers (with no effect), we tried clear rules, we can see the free/busy info in the calendar and contacts.

I created a new mailbox and tested to see if the issue only applied to old mailboxes and I was able to recreate the issue

It all looks fine but it doesn't work right...

What do I try next? 

On the mailbox store server have you checked that the "Microsoft Exchange Mailbox Assistants" service is running? If it isn't then start it.

That service controls, or at least is involved in the workings of Out of Office among other things, and that's been the cause when I've seen that exact same issue.

Our mailbox servers are all running that service.

Would it be needed on any of the other servers?

We have also found that our GAL isn't updating, if this has anything to do with this...

Well I've only ever seen those symptoms on our mailbox servers, never the CAS servers, but I don't know if that means CAS servers can't be affected.

Not sure if there's a connection with the GAL updating, and whether the Microsoft Exchange Mailbox Assistants service is involved in its operation, but I do know that OAB updates (the offline copy of the GAL) requires that service to run, so I guess it's possible.

Failing any better ideas have you tried restarting the Microsoft Exchange Mailbox Assistants service on your mailbox servers? If something's gone wrong there that's preventing things updating it's conceivable that it might not be bad enough to stop the service itself. Fortunately the service handles backend tasks like updating OoO states etc, so won't affect your users ability to access their email (in the past when we've seen the service stop it's been hours / days before we noticed because everything else kept working).