When "An administrator must always approve the comment" is enabled in Dashboard -> Settings -> Discussion, a commenters subscription is set to YC or RC (C = inactive) until the comment is approved, at which point it changes to Y or R ("All replies" or "Replies to comments").
However, there are a few big catches with this:
1) If you reply to an unapproved comment within the WordPress Dashboard and then press the "Approve and Reply" button (thereby approving the comment and then posting your reply in one go), the person never receives a notification of your reply because their status was RC or YC (C = inactive) at the time of your reply. The only way around this is to first approve the comment in the WordPress Dashboard (which changes their status to Y or R) and then post your reply. With a lot of comments, adding the extra step can get time consuming!
2) If you're using the WordPress iPhone App to approve comments, their status never changes from YC or RC to Y or R when you approve the comment. If you do approve a comment from the mobile app, you need to manually go into the WordPress Dashboard, navigate to the Subscribe to Comments plugin, and then manually change their status to confirmed.