Better performance with (Recompile) option, How? I've got a query which runs for 1 hour without any query hint, But executes in just 2 seconds flat with the "Recompile" query hint. When I got a look at the actual execution plan produced by both the queries, The query without the "recompile" hint has got more Table scans(It's actually a huge plan, and there were are a lot of scans).

To make sure the query plan is not being used from the plan cache and to rule out parameter sniffing, I cleared the entire cache using DBCC Freeproccache and did the tests again, Still no difference!.

So, From my understanding, 

With Recompile option tells SQL server not to cache the Query plan and generate a brand new one.(Result : generates a good plan and Performs well)

Without recompile option tells SQL server to reuse the plan in cache if it's available(but it's not there since I cleared the plan cache), or generate a new plan.(Result : generates a bad plan and Performs poorly)

So in both the cases SQL server will be generating a brand new plan, why the difference in plan and a humungous difference in performance all with just an extra Recompile option!!!!.
What's probably going on is that you're running the query with different input values in your parameter. Let's look at this simplified example:

SELECT columns FROM table WHERE something=@var;


This query might return zero rows, a single row or millions of rows, depending on the value of @var. The first time you run this query (without RECOMPILE), SQL Server generates a query plan based on the value of the variable for that execution.

Suppose that value of @var returns a single row, the query can afford an execution plan that takes 0.1 seconds for each row it returns, completing your query in 0.1 seconds total. Now, if you apply that same plan to another value of @val where the query returns 1000 rows, that query is going to run for minutes and you would probably be better off with another plan, perhaps with different joins, aggregates, etc.

When you use WITH RECOMPILE, SQL Server will evaluate the query (and the variable values) every time it runs and recreate the execution plan every time. This will add a few milliseconds to each execution (to generate the plan) but the resulting plan will probably be better suited for your particular value of @val.

If you're fine with an execution time of two seconds, this won't be a problem. However, if your query needs to complete in milliseconds, I would start tuning indexes, updating statistics, etc.

In summary, yes, this sounds a lot like a parameter sniffing problem, and WITH RECOMPILE appears to be a good solution in your scenario. I can't make any more qualified guesses without looking at query plans, tables and indexes, statistics and the different parameter values. Hope that helps.