That's the distinction. Is it money or is it a fenced good?
If I'm receiving currency (be it real money or bitcoin), I'm not going to think about where it came from. It's fungible.
This was in a small town bank, and I'm sure that larger banks have more sophisticated policies. I'm curious to know if ATMs have any similar features.
Yes, this can happen. Especially for higher valued items
Welcome to anti-money laundering law. KYC regulations basically mean, for anyone handling large volumes of money, it's the vendor's business, and liability, to know where customers' money comes from.
Exchanges do know the identities of a small fraction of all addresses, that's true. But if someone wants to remain anonymous, and has a relatively small amount (in relation to exchange's liquidity), it becomes trivial to hide the money.
Something like MtGox amounts are much much more complicated to clean in their entirety, that I agree with.
The bitcoin tumbler is a service that does the mixing, and as long as it has more than one customer, it can do the mixing.
A tumbler only helps if a lot of people with legitimate BitCoins frequently mix them in, so that people with coins from a mixer have a plausible claim of innocence. If mixers are primarily used by criminals, you've only anonymized which crime you've committed, you haven't really laundered the money. If those coins touch your real-world identity, you may not be incriminated in a particular crime, but you've made yourself into a suspect in a relatively small pool of crimes.
Beyond that, you could buy legitimate bitcoin and only use it to 'legitimize' mixing pools.