About three years ago, when the Xbox 360 was getting close to launching, we went through a security pass of the audio and photo playback capabilities. One of the tools that was recommended to us by another employee was the Codenomicon suite of test files. The folks at this company have taken the time to pick apart some of the typical file formats and produce an extensive library of files which target the specification and common implementations in an attempt to push the limits of your software. Unlike random fuzzing tools, these guys have gone in and hand crafted the files to exercise your implementation in a systematic and precise manner. And one of the major benefits over fuzzing is that you actually get documentation for each test case describing what is interesting about the file.
After running the files through the Xbox's code base, we actually found a couple of edge cases that weren't being handled correctly and warranted a fix. One of the interesting bugs was around an integer overflow that led to memory corruption. We would do some size calculations which resulted in a 32-bit unsigned integer overflowing to zero, which was then passed down to malloc. The cool (from a twisted perspective) thing about malloc(0), is that it actually allocates zero bytes of memory for you and hands back a valid pointer. But unfortunately for us, we would then go and try to write to that pointer which doesn't take very long before something horribly bad happens as we trash memory.
I think it is a fairly accurate statement that you can never do enough testing, and you should definitely try to use all the tools at your disposal. The Codenomicon suites are one such example, and something that not very many people I've talked to have heard about, so it is certainly worth investigating for your product.