Execution slow in stored procedure; fast when run ad hoc

I am dealing with an issue that I can't seem to solve. I was given this stored procedure that has speed issues. It takes 35 seconds or so. When run *adhoc*, it completes instantly. This made me think it was something to do with parameter sniffing. I have tried rewriting this to use local variables, optimize for unknown\variable\etc, with recompile. The table the scan is happening on is massive, but even with stats updated with fullscan, estimates are still WAY off. Perhaps the query could just be rewritten but I would like to figure this out. *ad hoc* plan - https://www.brentozar.com/pastetheplan/?id=Hkvg5Ge40 Parameters for *ad hoc* - SP plan - https://www.brentozar.com/pastetheplan/?id=S1w49GxER Parameters for SP - --- Parameters come in as:

(sp name)
    @ TransactionId VARCHAR(32),
    @ Category VARCHAR(4000)
AS

DECLARE
    @ Hash VARBINARY(16) = HashBytes('MD5', @Category);

The same values are passed in both the SP and *ad hoc* version. I thought it might be due to something with the hash being created as a local variable from the passed parameter, but in the *ad hoc* version it's doing the same (to me).