How about this:

DECLARE @NewBudgetID INT

IF (Select Min(BudgetID) as NewBudgetID from tblBudgetYear) > 1

Set @NewBudgetID = 1

ELSE

Select @NewBudgetID = top 1 BudgetID + 1 from tblBudgetYear x

where not exists(Select NULL from tblBudgetYear where BudgetID = x.BudgetID + 1)

order by BudgetID

On the occaisions where the value 1 is available, the longer query doesn't execute.