I once read that anyone who actually finds a SHA256 collision should publish it in a paper. SHA256 collisions are supposed to be the just shy of impossible to find (you know, the whole old trope of millions of machines millions of times faster than the ones we have now working for millions of years will find a collision at some point). Some confirmation of this would be welcome.

I don't like the way they present the result of how unlikely hash collisions are... The number (2-256) gives much more comfort than saying:

If you hash 4KiB-long blocks, then every possible block will share the hash value with (on average) 128 different 4KiB blocks. And on a standard 200GiB disk you can fit (more or less) 52,400,000 blocks.

This explanation is a bit less reassuring. Now consider the fact that your data is never random and you hit the same patterns all the time (loads of zeros / ascii letters / x86 code)

The same patterns thing is mitigated by the property that changing one bit in the input is (supposed to) change on average half of the bits in the hash.

You can also be reassured that there's lots of research going on about how likely these collisions are and how to find them. People are actively trying to break these hash algorithms, so it's not just in theory.

Happily, they have a 'verify' mode which checks the data on disc instead of making the assumption that SHA256 works as promised.

They do, but what I'm interested in is if it's something that actually occurs in real data (with SHA256, in the article he says that it's of more use with "worse but faster" hashing algorithms).

My initial remedy is to add another hash method and name the data based on the results of both; that way problematic data would need to trigger a collision in two different algorithms at the same time, which "should" be next to impossible. Currently my file fragments are named "{SHA256}.dat", in v2 I could instead name them "{SHA256}{SOME_OTHER_HASH}.dat".

Regarding the "should" part: http://stackoverflow.com/questions/1323013

Good stuff! Perhaps it's safe to remove the "" qualifier from my assumption.

NetApp and Data Domain are both enterprise-level dedupe vendors who use similar hash functions to find unique strings of bits. Check out their whitepapers. Short answer: not in a million years (and there are further checks in case the hash alg somehow failed.)