Optimize SQL Server 2005 Procedures

I had a stored procedure which took about 3 minutes to run, but starting this query in the management studio of sql server took 2 seconds! The problem lies in the "parameter sniffing". Google it for the exact cause, but copying the parameter variables to local variables within the procedure like the example below does the trick.

Slow procedure:

CREATE PROCEDURE GetMeMyData
@param1 NVARCHAR(20)
AS
BEGIN
SELECT id, name, otherstuff
FROM dbo.table1
WHERE param1 = @param1
END

Fast procedure:

CREATE PROCEDURE GetMeMyData
@param1 NVARCHAR(20)
AS
BEGIN
DECLARE @localParam1 NVARCHAR(20)
SET @localParam1 = @param1
SELECT id, name, otherstuff
FROM dbo.table1
WHERE param1 = @localParam1
END

At first I tought it had something to do with an outdated version of SQL Server, but it even occurs on SQL Server 2005 SP3.