If the statistics were "bad", or insufficiently sampled, why would running the query with the recompile option help?  You'd be making a new query plan with the same bad or incomplete information, and I would think you'd come up with the same ill-chosen query plan.

I believe RichardReynolds is correct in concept though.  If your table is not made up of homogenous data, you need to sample at a much higher rate than default.  Because I believe that's true, we rebuild all indexes each week (on Sunday where we have very few users online).  That gives us a complete statistics sample every week.

Still, we see the same problem described here.  Even with proper statistics, once the query plan has been built and cached for the first set of data it encounters, it seems to be reused even if statistics would show that it should be be reevaluated for another set of parameters for the same query.  We use the option recompile for several such Stored Procedures.

My opinion is, that the query plan does not get automatcially recompiled when a quick glance at the spread of data for a given set of parameters would indicate that it should.  In my mind, this is in the "bug" category.