Uniqueidentifier Causing Strange Execution Plan

Can anyone help me with this strange problem please?

I have a stored procedure, with a parameter defined as a
uniqueidentifier. The procedure does a select with a number of joins,
and filters within the Where clause using this parameter.


(@orderHeader_iduniqueidentifier)

SELECT*
FROM originalOrderHeader ooh
INNER JOIN originalOrderLine ool
ON ooh.id = ool.id
FULL OUTER JOIN orderLine ol
on ool.id = ol.id
AND ool.productCode = ol.productCode
where (ooh.id = @orderHeader_id)


There is a clustered index on the id column of originalOrderHeader,
and on id and productCode of both originalOrderLine and orderLine.
These indexes are regularly rebuilt. The execution plan shows a seek
against these indexes, but the estimated row count values are huge,
and should be single figures.

If I change the SP to accept the parameter as a varchar, and then
explictly cast back to a uniqueidentifier in the where clause, the SP
runs much, much quicker, the execution plan is doing far less work,
and crucially the estimated row counts on the clustered index seeks
are correct (single figures).

Does anyone have any ideas what might be causing this?