I think jeff might be onto something - as soon as I started reading his message I had the words "parameter sniffing" popping up
index hints is also a valid tool to play with (with caution same as join hints) - but to rule out parameter sniffing you can proxy your params like so
create proc x @id int
as
declare @id_new int=@id
begin
select * from table where z=@id_new
……….
there are also some settings on each database that control parameter sniffing
at least you now have a few options to test - let us know what you find