Is it a parameter sniffing problem?
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.