Those are good workarounds, and it might be what we will end up doing. The SQL statement is something like this:

select someID, right ('0000000000' + convert(varchar(10), a.someID, 10)) +

convert (varchar, dbo.CheckDigit(right('0000000000' _ convert(varchar, someID),10)))

from my_table as a inner join some_other_table b on blah = blah

where some_column not in ('a', 'b', 'c');

EDIT: Both "blah" columns are bigint, and have a clustered index on them.