Given that Google has been sued over that countless times, as a small startup I would be wary of following their example.

This is probably the wrong attitude towards founding startups. In general, you shouldn't unnecessarily risk the business -- but if people are throwing roadblocks in your way, lots of startups seem to generally do pretty well when they play fast-and-loose with rules. The logic is that nobody's going to bother to sue you until you get big and can defend yourself. Obviously taking a big risk like this isn't ideal, but you shouldn't let it stop you from moving forward with a business.