I want to have a record of associated contacts who have been removed from a deal. I can get property history for other deal properties, but not for associations.
You're correct; it's not currently possible to pull a history of object associations. I can totally see the use case for that, though; I'm happy to pass this feedback along internally, but if you have the inclination, I would encourage you to check out the Ideas Forum on the HubSpot Community. There, you can create a post including your use case that product and other customers can see.