The mistake I made was assuming that $form_state['values'] always contains all the values the user has input so far. It doesn't, but $form_state['input'] appears to. So, if you want to render a form element according to the current state of the form: test the contents of $form_state['input'], not $form_state['values']. If the form is rebuilt (due to an custom ajax callback, or file upload, for example) $form_state['values'] will change and can't be relied upon.
Edit: Be careful using $form_state['input']
as it contains untrustworthy, raw input from the user.