I think I have a parallel that explains Mark 16:16. Suppose I state, "All people who are enrolled and live in the dorm are students in the college. If John is enrolled, but doesn't live in the dorm, does that mean he is not a student?" Similarily, Mark 16:16 says "He who believes and has been baptized shall be saved." So how can you say that a person who believes and has not been baptized is not saved?
The parallel is an interesting one, but it is not complete. The choice of items contain built-in suppositions which lead to a particular conclusion. Allow me to give a similar parallel based on a different set of pre-suppositions. "All people who are enrolled and have been accepted are students in the college. If John is enrolled, but hasn't been accepted does that mean he is not a student?" In your example we would say "Of course he is a student!", but in my example we would say "Of course he is not a student!" What caused the difference in the conclusion? It is not the construction of the statement, but the information implied by the phrases.
In symbolic logic, the statements would be presented in this way:
p & q -> r [if p and q, then r]
p & ~q [p and not q]
~r [not r]
The first statement is an implication -- "If A then B". The truth table for an implication is
If the condition is true, the conclusion cannot be false. However, notice that if the condition is false, we cannot state whether the conclusion is true or false. In our original condition, there are two facts joined with an "and". In order for a conjuction to be true, both facts must be true. If either fact is false or if both facts are false, the conjoined facts are false. Hence, as soon as either clause of the conjoined condition is falsified, we cannot state whether the conclusion is true or false.
In the first syllogism, "All people who are enrolled (p) and are living in the dorm(q) are students (r). John is enrolled (p), but is not living in the dorm(~q). Is John, then, not a student?", there are several implications. We know that only enrolled students can live in a dorm (q -> p). We also know that students are not required to live in the dorms, so all that is required to be a student is enrollment (p->r). It is because of the last implied knowledge that causes us to conclude that John is a student. It is not the original statements that lead to the conclusion, but the implied facts.
In the second syllogism, "All people who are enrolled (p) and have been accepted (q) are students (r). John is enrolled (p), but has been accepted (~q). Is John, then, not a student?", there are once again several implications. We know that someone who never enrolls, cannot be a student (~p -> ~r). We also know that someone who was not accepted cannot be a student (~q -> ~r). It is the last implied fact that causes us to conclude that John is not a student. The original statements did not lead to this conclusion, it was implied additional information behind the statements.
What does this mean for Mark 16:16?
Jesus had stated: "He who believes and is baptized will be saved; but he who does not believe will be condemned." In symbolic terms this is:
p & q -> r
~p -> ~r
In other words, belief (p) is a necessary condition for salvation (r). But is baptism (q) a necessary condition for salvation? The plain answer is that there is insufficient information in just these two statements to draw a conclusion one way or the other. By Mark 16:16 alone you cannot state positively that baptism is not necessary, nor can you state that baptism is necessary. To answer this question, we must look elsewhere in the Scriptures regarding belief, baptism, and salvation to find the answer.
"For you are all sons of God through faith in Christ Jesus. For as many of you as were baptized into Christ have put on Christ" (Galatians 3:26-27). Using the same symbols used in Mark 16:16 and understanding that being a son of God and having put on Christ both are terms equivalent to being saved, we have the following:
r -> p
q -> r
What this means is that if you are saved, then you must have belief (the same conclusion we can draw from Mark 16:16). In logical terms, we are saying that belief and salvation are equivalent. You cannot have one without the other. But now we have an additional fact, baptism is a condition of salvation.
"Or do you not know that as many of us as were baptized into Christ Jesus were baptized into His death? ... For he who has died has been freed from sin" (Romans 6:3, 7). Puting this in logic we have:
q -> s
s -> r
Since baptism implies dying and dying implies salvation, therefore baptism implies salvation. Hence, baptism is a condition of salvation.
"And now why are you waiting? Arise and be baptized, and wash away your sins, calling on the name of the Lord" (Acts 22:16). Here again we have:
q <=> r
r -> t
Baptism is equated to salvation. To wash away your sins is to be baptized. To be baptized is to wash away your sins. Therefore, you cannot have salvation without baptism.
"There is also an antitype which now saves us--baptism (not the removal of the filth of the flesh, but the answer of a good conscience toward God), through the resurrection of Jesus Christ" (I Peter 3:21). In symbolic terms, this statement is just as blunt as Acts 22:16. It is saying that baptism is equivalent to salvation. You cannot have one without the other.
What we now have is:
p <=> r [ Belief is equivalent to salvation ]
q <=> r [ Baptism is equivalent to salvation]
If we stopped there, we could conclude that there are two paths to salvation. One through faith and another through baptism. However, Jesus' statement in Mark 16:16 ties the two points together. It takes both belief and baptism to gain salvation. In other words, there is no true baptism if it is not accompanied by belief and you cannot truely claim belief if you are not willing to be baptized. Or, as James said, "You see then that a man is justified by works, and not by faith only. ... For as the body without the spirit is dead, so faith without works is dead also" (James 2:24, 26). There are not two separate paths to salvation, but one and that one path includes both belief and baptism.