What are the assumptions behind calculating the market equilibrium from supply and demand curves?
Public information about prices--not necessarily about costs or willingness to pay--is indeed the key here. 

If S5 is willing to sell to B5 at $1, she must also be willing to sell to any other buyer at this price. Given the low price, there would be an over-demand for the unit sold by S5, and a resulting upward pressure on the price asked by S5. 

Similarly, if B1 is willing to pay S1 $5 for a unit, he must also be willing pay the same amount to the other sellers for one unit. Then Sellers with lower costs will rush to compete for B1's business, thereby creating a downward pressure on the amount bid by B1. 

The process settles when the market reaches equilibrium described by your second scenario, where three units are traded at $3/unit. 

In Vernon Smith's canonical market experiment (and countless replications thereafter) wherein buyers and sellers with varying values/costs trade in a double auction,  the equilibrium outcome predicted by theory, rather than the assortative matching outcome described in your situation 1, is observed. 

This is also related to the Law of One Price.