Stored Procedure with HINT "WITH RECOMPILE" loses performance, solved with DBCC FLUSHPROCINDB
The hint WITH RECOMPLILE is telling your database to rebuild the execution plan every time. This rebuild requires some overhead, and can explain why it takes an extended period of time in some circumstances. Determining exactly why and when the recompile takes longer will require more information from the system (ambient load, how much change there is in the tables being analyzed, table contention, etc).

A more detailed explanation can be found here. 
https://stackoverflow.com/questions/20864934/option-recompile-is-always-faster-why