As others have mentioned, the app can have a button to report a cleanliness issue. Working back from the first report means you don't have to review 12 hours of footage. As a side note (since this is HN), you don't have to review 12 hours linearly, you can use a binary search, which means you can probably find the culprit in minutes at most.
Fortunately, I can get that done for me at a cost of much, much less than 12 hours of my own time. I can farm it out overseas to somewhere with a large supply of very cheap labour. I wouldn't be surprised if sitting in front of a bank of a half-dozen taxi-interior replays running backwards at triple-speed (with the empty periods already taken out by some relatively simple processing) from a point at which the uncleanliness is visible was seen as a good job, compared to some other options available.
Wouldn't be surprised if I could have that done for me at a cost of a few dollars a time; if I then charge the culprit a hundred bucks on their already registered credit card or taxi account for cleaning (fifty sounds too low), it becomes very economical for me.
You know exactly what time your customers entered and left the vehicle. All you have to do is pull out a set of freeze frames from before and after each customer and compare the two.
I mean, we have to deal with shitty customers all the time. 99% of the time it's just not worth pursing someone who broke something or just left a mess, even if theoretically I could hunt down proof that they did it. It almost always escalates to some multi-month situation that is not worth the effort.
If someone becomes a multiple offender, you ban them.
Simple.
The cars are going to have cameras constantly running in them.
Which of course creates a self-perpetuating problem, because if the behaviour is not punished, it will never be corrected and it will become "ok" to make a mess in an auto taxi(not vomit, but just leaving your rubbish behind).