I found a solution: a) don't validate
replaceDataSource (last parameter is False instead of True), and b) use
SaveToLayerFile which has a "relative" parameter instead of
lyr.replaceDataSource(target_wspace, 'FILEGDB_WORKSPACE', lyr.datasetName, False)
arcpy.SaveToLayerFile_management(lyr, fixed_fname, "RELATIVE")
Unfortunately it doesn't work with group layer files, but at least it's progress!
For your info and to avoid confusion, as the apparent contradiction certainly confused me at first, in the Esri doc Paths explained it states unequivocally that relative paths are not supported in scripts while the reference page for Save to Layer file says just as clearly there is a RELATIVE keyword.
What this means in practice is that yes you must use full path notation in scripts,
x:\data\foo.gdb and not
..\..\data\foo.gdb, and then saveToLayer strips the drive letter and leading directories on save. So the inputs must always be full paths, while the output may or may not be.
As far as I can tell SaveToLayerFile is the only arcpy command with a relative parameter. I presume there is an equivalent for saving mxd's but I haven't found it yet.