It's been a while since I played the GameBoy and NES versions, I'll have to go back and see what Mayhem 4's like. I was able to solve every level in both versions, though I certainly will believe you when you said a solution in NES version doesn't work on GameBoy version, since I know I've encountered a few myself.
The NES version is actually worse in some ways. It is mostly very similar to the GameBoy version, but the lemmings walk a bit faster if I recall correctly And there was one level on NES I particularly remember where I think it has high save percentage (much lower on the GB version) and a high effective release rate, except the high release rate doesn't match the low release rate number shown on the pre-level screen (suggesting it was probably a bug and got set higher than intended), making the level pure hell to execute (nearly to the point of impossible)*
Those two versions was interesting to me as a curiosity and a somewhat-sadistic-at-times challenge, but yeah, not exactly the ports to recommend for normal, fun play.
*Some of the details described may be slightly off due to memory from long ago, the main point is that there is a noticeable discrepancy in one of the numbers shown on the pre-level screen vs the actual effect experienced when you play the level, and the overall result was a nearly impossible level that probably wasn't intended as such.