Rebuilding index gets you a 100% refresh of statistics. I would be willing to bet (without additional information) that this is a stale statistics issue whereby the optimizer doesn't "know" about a particular parameter value due to stats being out of date and it "guesses" and gets a bad plan (scan from the sound of it).

Make a job to nightly refresh stats on that one table and see if that helps. Use Ola.Hallengren.com's AWESOME maintenance suite for this. VERY amazing, FLEXIBLE, DOCUMENTED and FREE script suite for handling all your maintenance needs.

BTW, I have some clients that run stats updates as frequently as every hour on some critical tables. The auto-update rule of 20% modified rows just doesn't cut it in MANY MANY cases!! Statistics are the core underpinnings of the optimization process, and if they aren't valid per current data, nothing good will happen with your queries! 😎