Yep. It was something obvious.
You can't delete files from the Solution while it is building.
I just tried again and the Delete option magically reappeared. I realized that it has stopped a build since I last tried.
In short, there are three different angles that a user can try to delete a file while a build is occurring and the behavior is different for each.
- Undo the file add from Pending Changes -> Nice error messages are given.
- Delete the file from Source Control Explorer -> It lets you remove the file as I described in the question but leaves it on disk and in Solution Explorer (same behavior regardless of whether or not a build happening).
- Delete the file from Solution Explorer -> It quietly prevents you from shooting yourself in the foot and doesn't explain why.
The right way to do this is to cancel the build (or let it complete), then delete from Source Control AND from Solution Explorer.