It's unlikely to be a "static" bug affecting everyone because it would've been caught in QA and/or user reports and fixed already (this is not a new issue, been happening for a year at least).
Therefore my hypothesis is that it's dependent on corrupt persistent data that a relative minority of users have which is not easy for Apple to detect/replicate.
Since the macOS Messages app is some Catalyst abomination, it won’t even support expected keyboard shortcuts for navigation, selection and deletion. Having to do everything using the trackpad is a slow process.
It’s frustrating that messages is so bad.
Even in open source apps where in theory we can contribute functionality like Signal it’s difficult. E.g. it’s impractical to delete lots of media in groups in the iOS app. I added a PR last year to help this but still waiting for a merge even though it has been approved :(
Edit: PR for the curious
And this is why they (and many companies) behave this way, there's no incentive to fix a problem that you will just pay them more money to fix. Fixing the bug means reduced revenue. Complaining about the problem sadly won't help, you can only stop using the app and stop buying their products.
The user’s options are quit the ecosystem or pay up. Apple’s lock-in monopoly means they get to shove their customers into another monthly fee.
This is a classic example of the harm done to consumers by allowing anticompetitive practices. (The consumer has no choice but to pay)
When the US government gets off their butts and investigates Apple for antitrust, this will be one of the key findings. The fine should be some multiple of the amount of money they have illegally extracted from their customers.
Same with HomeKit Secure Video (HKSV). The only way to access recordings is through the Home app. I'm surprised nobody has figured out a way to browse them outside of the app.
I have a very similar issue with iMessage in iCloud, and unlike photos, there’s no web interface. You have to interact with it on your device. Thankfully I have a Mac so I can load up the chat database from there and see what’s using the space, but cleaning it up has been a nightmare: I have a script to find the big attachments, but if I delete them then some agent that manages the database goes into a loop for like five minutes per deletion. Then the change gets synced to iCloud (at least, I assume). So unless I fully reverse what the deletion process does and whether it is possible to do a batch operation I’m basically at the mercy of the front end they provide to clean things up, which as I mentioned earlier is absolutely not designed to make it easy to do this.