Apple Mail's "Remove Attachments" not removing attachments from hard drive
I stumbled onto a solution after several hours. Hopefully this can help others. 

Background

I wanted to remove attachments larger than 1MB from emails older than 5 years. I made a smart mailbox with criteria for "has attachments" and "date recieved not in the past 5 years". I did a "select all" on the ~25k results and chose "Message > Remove Attachments" from the menu bar. Mail chugged away for half an hour, and afterwards the attachments were removed from the email messages, but the "Library/Mail" folder hadn't changed in size. Drilling into the "Library/Mail" folder structure in the Finder, I confirmed that the files were still there.

The missing step

I have my email sorted in folders in the Mail sidebar:

On my mac
     Project 1
     Project 2
     Etc


In order for the removed attachments to actually be deleted from the file system, I had to click on each folder in Mail's sidebar. Something about opening the folder in Mail seemed to cause that folder's messages' removed attachments to be deleted from the file system.

**Important to mention that this was using a POP email account, and the messages were long ago deleted from the server, so there wasn't an issue of Mail re-downoading the attachments from the server.