That still does not resolve the issue of someone having a job_id parked in some code somewhere and that job_id ceasing to exist when a job is dropped and recreated. Maybe I am confused...why would you ever be working directly with a job_id to call a job remotely? I would not bother with an extra function or round trip to resolve an ID. This should suffice and survive the scenario where someone drops and recreates a job:

DECLARE @job_name SYSNAME;

SET @job_name = N'My Job Name';

EXECUTE [LinkedServer].msdb.dbo.sp_start_job @job_name = @job_name;