Could you add an IDENTITY column to the actual table itself, and include that in your composite key instead?
It sounds like you are doing
EXEC MySP_GetID @TheID = @TheID OUTPUT
INSERT INTO MyTable(Col1, Col2, ... ColID)
VALUES(@Col1, @Col2, ... @TheID)
and code from other places is also using the MySP_GetID, probably for other tables, and that is causing the deadlock (NOT the act of using Scope_Identity() )