The icu recipe installs icu-native twice, once in the usual location, and once for cross builds into the path given by --with-cross-build. This latter path is not included in the list of paths recognised by chrpath.bbclass, hence the binaries in there retain the rpath as used during compilation. This causes the package to not be relocateable from sstate.
Created attachment 2191 [details] fix hard paths using PREPROCESS_RELOCATE_DIRS
It seems this change alone doesn't cause the sstate signature to become invalid, hence bitbake uses an existing archive from sstate (which still has the old rpaths). Not sure what's missing to force a signature change here, other than doing a -c cleansstate
And BTW, in the patch, I did try using ${STAGING_ICU_DIR_NATIVE} instead of open-coding ${datadir}/${BPN}/${PV}, originally, but that didn't work, as at the time chrpath.bbclass was running, this translated into .../usr/lib instead of .../usr/share (as it should and does during all the other tasks). I didn't find the reason for that.
Andre, can you submit this to the oe-core list as a git-formatted patch?
Fixed in oe-core e7fcaa534511e3f65b630b01cf0c824ee5a5fd4d.