BFD: st4lu6Am: Not enough room for program headers, try linking with -N
mipsel-linux-strip: st4lu6Am: Bad value
Other shared libraries could be successfully stripped.
The clue was that these shared libraries were generated with an earlier toolchain that used an older version of binutils.
It turns out that this is caused by binutils-2.18 wanting to add a NULL segment even when the binary didn't originally have one. Applying the fix makes the problem go away.
I only really mention this because the fix description doesn't contain the error message I saw thus making it hard to Google for a solution.