OK, stick with me here... I have read so many web-articles about issues like mine, all with different solutions and fixes, I am thoroughly confused. This is what happened:
a) A few days ago, we realised that new Exchange users were not showing up in Global Address List
b) Outlook (2010) runs in cached mode here, so flipped it out of cached mode, and ALL NEW USERS show up fine
c) Put it back into cached mode.
d) Opened cached GAL, and noticed that if I change the view FROM "Global Address List" TO a specific address list (i.e. "All Users") then the new users DO show up.
So... I appear to have an issue ONLY with the Offline Address Book/Default Global Address List.
All other address lists work fine.
Unfortunately, telling 9000+ users to switch address lists each time they want to see all users just isn't going to cut it... Also when drafting email, typing the name of a new user and hitting CTRL+K does not name match these new missing users (so I assume it looksup against the Default Global Address List).
I have tried the obvious stuff like updating the Offline Address Book via EMC and PowerShell, no joy.
Does anyone have any ideas how to fix this? Or what the next logical troubleshooting step would be?