So if the rover in has the effect of negating the whole thing anyway in both maleghbe''egh and malegh'eghbe', then what might be a reason for Klingons to say it one way rather than the other? Maybe they just say what sounds more natural to them. To me, the latter sounds more natural because of SuvwI'pu' qan tu'lu'be' in TKW. (This is what finally got me to switch from saying tu'be'lu', which originally seemed more logical to me, since I have no idea what negating -lu' would even mean. That, and I came to dislike the sing-songy sound of tu'be'lu'. But I digress.)

Another possibility is emphasis. Let's suppose Klingons usually say malegh'eghbe'. In that case, maybe Klingons say maleghbe''egh to mean "We don't see each other." To emphasize "each other," perhaps they'd just say malegh'eghbe' with more stress on the -'egh. (And to emphasize "we," there's malegh'eghbe' maH.)

~mIp'av