So properties have an ID in the database, but when they are loaded into the server they get a 'local index' ID on the server.
For example, properties in the database might be ID 1, 2, 5, 9 but in-game those will be in index 0, 1, 2, 3. When replacing vehicles, I was using the local IDs to delete vehicles from the database, but should have been using the database IDs.
I don't know if that's what caused this issue though. But it was _an_ issue that's fixed nonetheless. I will leave this issue open for a while in case it happens again.