The question seems to be worried in a somewhat inflammatory way, so I'm going to answer it in somewhat less inflammatory terms. Also, while it sounds like philosophy of religion because of the figures you picked, this is primarily just a matter of logic. Let's divide the question into different cases.
Question 1: Would two people making opposite truth claims necessarily be a contradiction?
The answer to this question is yes.
If Person A and Person B take the positions P and not P regarding the exact same claim then at least one of them is wrong per the law of non-contradiction. (I will leave living outside the laws of non-contradiction as an exercise for the reader).
So if A says that person C ate a banana for breakfast on July 12, 2014 and person B refers to the same Person C and says they did not eat a banana for breakfast on July 12, 2014 then at least one of them is wrong.
B: not P.
--> P and not P (= contradiction)
Question 2: Would two people claiming another person told them something where the two are told different things necessarily be a contradiction?
The answer to this question is not necessarily. The reason is simple. Let's say Person A tells you that Person C told them they ate a banana for breakfast on July 12. Let's say Person B tells us that Person C told them they did not eat a banana for breakfast on July 12. This is not a contradiction because what they are saying is not the same thing. A is reporting what they C told A. B is reporting what C told B.
P: banana breakfast
A: Q [ C told me P]
B: R [ C told me not P]
--> Q and R
Now, we need some means of unpacking Q and R to figure out whether this is (a) a contradiction, (b) a misunderstanding, or (c) that C is a liar.
In the banana case, we must conclude at a minimum, that either A, B, or C lied at least once. Because if we took all testimony as factive we would have: P and not P. So either C's utterance to A or A's recounting or C's utterance to B or B's recounting is false. But this or is not exclusive, everyone could be lying.
If Q and R turn out to be non-contradictory claims, we could still have but do not necessarily have lying going on. Say Q and R are about different years.
Question 3: if two people receive orders from the same person to do different things is that somehow contradictory?
Here, we need to refer to case 2, but we're left even further from the likelihood of a contradiction. Why? Because claim Q is now A says C told me [A] to do X and R is now B says C told me [B] to do Y.
A or B or C could still be lying, but now there's no logical set that makes the contradictory if all of them are telling the truth.
To make a contradiction, we would need to show that the content of X and Y are contradictory in a rather strong sense. Ex. that is not contradictory: A says that C told him to sweep the floor. B says that C told her to ignore the floor. Clearly not contradictory. Ex. that might be contradictory: A says that C said to exterminate people with glasses. B says that C says to send people with glasses to safety. C might be pretty twisted but is not necessarily being contradictory.
The following relevant type seems to belong here:
Case 3 Terms
A: C told me to tell M that Q.
B: D told me to tell N that R.
To show them contradictory there's a lot of leg work that would need to happen to show that Q and R are inconsistent a way strong enough to warrant that being contrary (so "plant in spring" and "harvest in fall" types of differences won't come into play). That M and N are relevantly similar groups to be being asked to behave in contradictory ways. That C and D are sufficiently identical entities, and that A and B are not the parties causing the transmission error.
Question 4: Mohammed and Jesus
I am not that familiar with Islam, so I can't directly address every detail of how Muslims understand this working out. But from what I gather Muslims read the statements of Jesus to have different meaning such that if they were to contradict Islam Jesus never said them. Thus, Jesus's claims to divinity are rejected by Muslims. So So if Jesus is B, then the claim is that B never said those things.
In other words, look at our case 3 terms, let's say the claims in Islam involve A, C, M, Q and those in Christianity B, D, N, R. They accept an identity between C and D counting Jesus as a prophet. They accept some differences between M and N. In cases where R would contradict Q, they reject that B ever said that.
For Christians, I generally take it that the identity of C with D is questioned. So it's kind of irrelevant what C told A to tell M, because the claims are not accepted as truly from God.
The sort of contradiction you claim never happens because the groups resolve around those claims in differing ways.
The claims at are not simply contradictory as in P and not P. But rather involving A says that C said to A to tell to M message Q. Sure, they can't both be true, but that would only be a problem for someone who has already accepted the truth of A's claims about being spoken to by C to tell to M message Q and B's claims about being spoken to by D to tell to N message R. But there's no requirement in either religion to accept the entire set of claims made in the other religion.