I worked almost exclusively at startups under an H1B in SV and know many many others. A company pays something like $5K for the legal services and fees to hire an H1B, and under normal political circumstances they receive the initial docs that lets the employee start working in 2-4 weeks. There is really no reason H1Bs wouldn't work at startups (and they do)