I've got a reputable SF lawyer (does YC companies to boot) to do formation+note+etc for ~$3k. Cooley/WSGR/etc will all look for $25k (and sometimes help by deferring), which IMO is outrageous. It's outrageous not because it's incorrect given the market, but they're value isn't high enough to justify the cost. If you're negotiating a Series C, I can see their value but not when you're just starting. Early stage law is fairly boiler plate, that is, unless of course patents come into play.

at that stage, patents are probably a waste of time for a startup, wouldn't you say ?

I guess it doesn't necessary have to be filing patents, but rather checking whether you'll be infringing any.

Isn't that exactly what you don't want to do, since infringement is almost impossible to avoid, and wilful infringement costs more?