Recently in one of my projects we had a vendor that would deliver code that they swore they tested and passed all validation tests only to have it fail on the first couple of tests every time. This was frustrating for us, since we were paying this company to test the code before sending it, and for them, since their reputation was getting hurt with each "bad" release. After they tested the code again and we tested the code again and we each received different answers, we decided to have a web conference to try to figure out what was going on. They started by creating a new entry and showed how everything worked fine and then we showed them our entry and how the code bombed with the first test.
I could see some lightbulbs go off when they realized we were using entries that were created with an old version of the software. I won't go into much detail about some of their suggestions other than to say that completely wiping out our database and starting over is not an option each time a new version of the software comes out (which is what they did before testing). So while they tested with entries created with that version and it worked great, they never tested against legacy entries. Imagine if everytime Microsoft released a new version of Windows you had to start over from scratch! <cough>Windows8 RT</cough> :)
The moral of this story (and it builds upon an earlier post about knowing your customer) is know your customer's data and make sure legacy data works as well. They may not like the idea of wiping out everything and starting over.