Does your proc have input parameters which then used directly in WHERE clauses or JOINS?

If so, try to declare local variables at the top of proc, assign them to input param values and use them instead. You may find it will help you better than using WITH RECOMPILE.

Do you run both ways in SSMS?