I just tested this on my own site. When logged in as an admin, if the enable personal messages setting is disabled, the Messages link is not shown on either my profile page, or on the profile page of any user’s preferences pages that I visit. I am not sure if this is a recent change or not.
As an admin, it’s possible to visit a user’s messages page by typing the messages URL directly into the browser’s address bar. For example, for a user with the username ‘simon’, I can access their messages at /u/simon/messages, even if the enable personal messages setting is disabled. This makes it seem to me that the Messages link should still be displayed for admins in this case.