I think the final piece of the puzzle was the Open Access List permission. It’s quite possible that this was in place before I mucked about with the address lists and caused my problems. Nonetheless, after overcoming the mailbox permission fiasco, average users were still unable to use the Global Address List.
I went back and checked the All Global Address Lists container, and sure enough, the Authenticated User permissions didn’t include this one. So I added it back in, and now it seems to be working just as expected. The problem with this is that it appears that users must be able to access the Global Address List in order to create their mail accounts.
There are methods to provide different address lists to different sets of users, but thus far I haven’t been able to get them working. I’ll keep hammering on it and let you know how it turns out (and, perhaps more importantly, if I find any way to do everything that I need to do).