Okay I figured it out. Posting the solution for others:
The images aren’t included in the media library that appears if you click the ‘Choose image’ button on the header configuration page (which seems like an obvious oversight to me), but they *are* listed in the full media library from the main dashboard bar: Media -> Library. You’ll see ‘Header image’ beside all of the files that were uploaded or selected through the header configuration page. Delete them and you’re good to go.
