Changing stored procedure parameter results slow stored procedure performance
One of the first things to look at in an actual execution plan, especially on the most expensive operations, is the estimated vs the actual row counts, executions, et cetera.

Often, when the estimated numbers are significantly off from the actual numbers, it indicates that the statistics for the table are out of date. This can cause the query engine to choose a bad plan. Based on what it knows about your data, the plan makes sense; however, enough of the data has changed since your statistics were last updated that the plan's not the best option for actually returning your data.

If you don't have a job that regularly updates statistics, trying updating the statistics on just this one table (or, more likely, the tables involved in this view), and see if the query speed becomes more predictable. I'd recommend setting up a statistics update job to run on a regular basis (probably at least weekly).

Note that, as the stored procedure is recompiled each time through, some time is spent calculating that optimal plan. If the speed of the stored procedure becomes more predictable, you may want to consider trying it without the WITH RECOMPILE; depending on the complexity of the query, the cost of the recompilation might be higher than the cost of using the same plan with different parameters.