IP law firms use automated software to scrape the trademark registration filings at the USPTO and other national trademark offices (ex. [1]). These software services automatically assess filings for possible infrigement. This is the most likely way for a bigco's lawyers to find out about your logo or company name - far more likely than them finding out about your startup from techcrunch or some other source.
Unfortunately for me, this happened to me. I was able to negotiate a coexistence agreement for my logo, but I could have done without the pain. If I were to start over from scratch, I would seriously consider doing the Apple/Google offline foreign filing trick [2].
[1] http://towergatesoftware.com/
[2] http://blog.altlegal.com/tongan-shell-game-how-apple-and-goo...