A recent reinstall of Exchange and now when I try to load the GAL in Outlook, error says The Bookmark is not valid.
I'm pretty sure this is a permissions issue, but I don't know where to look.
I suspect you have some OAB issues, since this is what Outlook actually uses when you're in cached mode.
It would be good to turn up the diagnostic logging for the OAB generation process and do a manual rebuild of the OAB. Hopefully the error will come to light in the event log. If you need to paste warnings/errors from your OAB Generation process into your original question, please feel free. When you're done with this, don't forget to turn the logs back down to normal.
It could be your OAB generation server is not what you expect and you need to move the OAB generation server to your new one.
If your OAB is being distributed solely by public folders, ensure the public folder database is mounted and available.
In ESM go to the Properties of the Global Address List and ensure that "Authenticated Users" have the appropriate permissions.