Why might SQL parameter sniffing have negative performance effect on first execution?

Why might SQL parameter sniffing have negative performance effect on first
execution?

I have a SQL 2005 database that is distributed with an application at
about 250 different locations. At just one location a stored procedure was
timing out. I found that the query within the stored procedure runs
instantaneously by itself in SSMS but the sproc takes over 30 seconds to
run it. This led me to reading up on parameter sniffing. The articles &
forums I've read explain that the execution plan will be created based on
the parameter value used the first time you run the stored procedure and
therefore may be inefficient for successive runs with different parameter
values. Makes sense. What I don't understand is, I have dropped and
recreated the stored procedure (even tried "with recompile") and restarted
SQL Server, then executed the sproc and it still takes 30+ seconds to run
on the first run and successive runs using the same parameter value every
time. Updating the sproc to copy the parameter value to a local variable
does fix it, but I don't understand why when I'm only using a single value
and all of the parameter sniffing examples pertain to using multiple
values for a parameter. Why might it be running slowly in this scenario?
I'm still working on understanding the execution plan to try to find where
the difference is, but I thought some of you could probably shed some
light on this behavior.