In particular, many states (e.g., NY) would only demand that a company collect sales tax if it had a physical presence in that state. Since Amazon had no warehouses in NY, it didn't have to collect sales tax here.

In NY, it's actually the purchaser's obligation to report tax that was due on mail order purchases where the company didn't collect NY sales tax - there's a box for it on the state income tax form. (But it's something that most people don't bother to report since it's difficult to enforce.)