Well, you can always do this manually in the ADUC - make sure you have View | Advanced Features checked. When you open a user in ADUC, go to the "Exchange Advanced" tab and check the "Hide from Exchange Address List" option for these users.
That said, unchecking the option in the SA should work - you might try checking and then unchecking and saving the user and see if that writes through just as a test.