if there is a location update rejection, it means that the MS performs a location update REQUEST. So the MS itself is not at fault.
The IMSI of those MS are rejected by the neighbor HLR, because their IMSI’s are not allowed in the neighbor PLMN. Perform a test by manually asking the HLR to “check” such an IMSI, and see what’s its response. I don’t know if such a test is possible though.
You can always perform an trace on the interface between your MSC and the distant MSC.