I ended up with very similar "Job item lost or destroyed. x539" spam when trying to sort out some animal overpopulation problems. Might be of help if the cause of the problem is similar? Here's what happened:
1) I channelled out a hole in the ground to chuck animals into.
2) I created an staircase down into the hole, seperated by a door set to "tightly closed" to prevent animals from escaping.
3) I created a pit/pond zone over the edge of the pit (1x2 zone, one grid over ground, one over empty space)
4) I assigned every single horse, cow and bull to be pitted (lots of animals). Dwarves started hauling animals and chucking them into the pit.
5) I figured (inspired by the wiki) that the process would be faster if I had more than one pit/pond zone giving out jobs, so I created a second pit/pond zone next to the first one.
6) I assigned every single horse, cow and bull to be pitted in the second zone as well. Here's where the problem started; I should of course have realized that the different zones couldn't know that they shared a physical pit.
7) Dwarves started running down into the pit to fetch animals that had already been pitted from zone #1 in order to pit them from zone #2. While silly and inefficient, this wouldn't really have been a problem.
The door to the pit started "leaking" when dwarves ran in and out, and animals started escaping.
7) To prevent dwarves from re-pitting animals, I forbid the door into the pit. My thinking was that this would lead to dwarves not accepting jobs to pit animals already in the hole, leading to a potentially frustrated zone but no major inconveniences and eventually all animals would be in the pit. This is when I started to get the same kind of "Urist cancels Pit Animal: Job item lost or destroyed. x12074" spam that the OP seems to experience. Also, my framerate got REAL crappy, probably not very surprising.
The reason I didn't report this before was that I had to act so stupid in order to get it to happen that I wasn't sure it was worth addressing. But if similar stuff happens in other situations it might help hearing what I did to cause it..
Some further reflects on my experience above:
A) Animals probably shouldn't be allowed to pass through "tightly closed" doors even if they're temporarily opened by dwarves. This to simulate dwarves acknowledging the "keep closed!" sign on the door and not letting animals through. Critters seem way to likely to sneak out of pits otherwise.
B) It ought to be possible to see whether an animal is currently pitted in the "assign animal to be pitted" screen for the pit/pond zone. The reason for this is that if a single horse escapes somehow, or a new one appears outside of the pit, it's hard to figure out which animals needs to be re-assigned to the pit/pond zone. Of course, since none of my animals in the example above was actually in the pit/pond zone, there may be no easy way to check this currently. Perhaps check if they're enclosed in a small area with no path out?
Anyway, hope this helps somehow.