I was able to replicate this issue in testing as well and I'll get it escalated to development for you now.

What is the mystery "Work Address" of 124?

I didn't see that particular behavior in my testing, and so I suspect this might have been a local contact hiccup that was triggered when the underlying error occurred. The issue is ultimately that Outlook requires that global directory functionality in a lot of areas, some of which we wouldn't expect it to require it for. I did a fair bit of testing yesterday afternoon in various areas (with the GAL disabled) to try catching any other problem areas and I don't see any trouble so far! If there is anywhere else you'd like us to test further just let me know!

@Kyle wrote, "The issue is ultimately that Outlook requires that global directory functionality in a lot of areas." 

So is this actually an Outlook requirement for MAPI functionality, and NOT a bug that needs fixing?
 

@Jay Dubb

That's interesting. I think my one domain, which is the oldest, has had GAL off for years (like 17 years), and MAPI has been working for the most part.

I don't know that it's necessarily an Outlook issue per se, just something they worked into their systems in such a way that working around it (when it is disabled) can be tricky.

Microsoft has been making some subtle changes to MAPI in the old Microsoft Outlook (not the new version that is funneling all your email through their servers). For example, searching in MAPI now uses EWS calls instead of MAPI calls. It's our job to keep adjusting to these changes as they arise, which we are currently doing. We have a workaround for the GAL issue that prevents sharing which will be released today and we should have searching changed over for a release next week.  It never stops!