There have been some ideas floated, most notably by Ed Warnicke, of
how we might be able to encode checksums of the source in binaries without
taking up too much space. I think these mechanisms should be studied, built,
and encouraged. I've even urged groups like SPDX to focus on this sort
of thing, as it would be much more useful than the current projects
they're doing.
Why not simply have the makefiles for the program in question do a shasum
of the source, put that checksum into some source file and have the file
linked into the binaries in a way that can easily be found. (e.g. you make
it so the binary contains some easy-to-find fixed string of bytes followed
by the shasum value)
Now some GPL violators will simply strip the feature out before shipping
but for those who don't, it will help in verifying that the source they
distribute matches the binaries.
Although I guess the question then becomes "what goes into the shasum"
