Obviously Google knows who your coworkers are. Only one of them searching for Roadhouse (combined with some other matching critera) might be the reason you see it.
Sounds plausible. No matter what they say, Google "stickies" some searches to IPs, even when you're not logged in and clear all cookies. This is one of the reasons I started using a VPN.
How does a VPN help? Unless you're switching IPs constantly, Google will still associate the information with you.
Your actual identity is irrelevant, it's the "virtual" identity they've built of you that's important.
If you use a VPN client on your computer/phone your searches won’t be associated with other searches coming from your office.
I think most VPNs use NAT, so many users share the same IP address. Otherwise the VPN would be mostly pointless.