I was thinking a bit about the performance problem I mentioned above when creating a sequence.

The group by querry could be rewritten so it can correctly use the indexec.

The following querry would do the trick:

 SET @tmp_invoice_id = (SELECT top 1 (SUBSTRING(invoice_id, 4, 5) + 1)

                        FROM Invoice WHERE (invoice_id LIKE @tmp_date + '%')order by  invoive_id desc)

This will limit the querry to only retrieve one record and only do one substring and one implicit cast on the data.