Is it a parameter sniffing problem? I have a stored procedure which is called by Console Application (C#), the sp do nothing much just checking the existing of the record and update it:

    ALTER PROCEDURE [dbo].[sp_Update_StaffTable] 
        @OldStaffId nvarchar(100)
       ,@NewStaffId nvarchar(100)
       ,@FirstName  nvarchar(100)
       ,@LastName nvarchar(100)
       ,@Description nvarchar(100)
       ,@WorkPhone nvarchar(100)
       ,@Photo varbinary(MAX)
       ,@UserType nvarchar(100)
AS
BEGIN

SET NOCOUNT ON;
if EXISTS(SELECT [StaffId] FROM [dbo].[StaffTable_Temp]  WHERE [StaffId] = @OldStaffId)
    BEGIN
        UPDATE [dbo].[StaffTable_Temp]
           SET [FirstName] = @FirstName
              ,[LastName] = @LastName
              ,[Description] = @Description
              ,[WorkPhone]  = @WorkPhone
              ,[Photo] = @Photo
              ,[UserType] = @UserType
              ,[StaffId] = @NewStaffId
         WHERE [StaffId] = @OldStaffId;
    END
END


The console application calls this sp and gets intermittent timeout issue when it updates the first record (we update for the whole table which contains around ~5k items).

I don't think 'parameter sniffing' is the root cause as the estimated number of rows is always = '1' for all scenarios, is it correct?

any help would be much appreciated
If it's the first UPDATE that times-out then I'd look closer at your physical reads.

If [staffid] isn't indexed then you'll be performing a full table scan and pulling the entire table from the IO subsystem through to the buffer.

After the first UPDATE most of the table's pages will be in the buffer and subsequent UPDATES will be able to perform logical reads for the EXISTS part of the SP.