Should an INSERT cause an exclusive lock on a foreign key?

Here's my first recommendation to remove the deadlock (and this is a very common cause with the same resolution every time). Your RoutePlan_Save procedure currently has this logic:

IF EXISTS (SELECT ... WHERE key = @key)
  UPDATE ... WHERE key = @key;
ELSE
  INSERT(key) VALUES(@key);

So you actually have two queries here that require locks on the table, regardless of whether you are ultimately going to perform an insert or update. Stop doing that! What is the point of checking if a row exists, and then in a separate query, firing an update statement that again has to check if the row exists? This requires more resources, not less, than just trying to update the row not knowing whether it exists. So do this instead:

BEGIN TRANSACTION;
UPDATE ... WHERE key = @key;
IF @@ROWCOUNT = 0
BEGIN
  INSERT(key) VALUES(@key);
END
COMMIT TRANSACTION;

You can also isolate the other read-only processes by using a different isolation level that doesn't require them to wait for write operations to complete. NOLOCK / READ UNCOMMITTED is a popular one, but READ COMMITTED SNAPSHOT - assuming you can take the hit on tempdb - is way better IMHO. There are other alternatives, too. I happened to blog about this just yesterday:

• Bad habits : Putting NOLOCK everywhere