Regarding Method 1:
Running this code against a table with 55,000 records took me 4 minutes (longer if you have more columns in your table).
I currently have a table with 17 columns, containing 278,998 records. The "key" field (used for URLs) is a varchar(8) filled with random alphanumeric strings.
Creating a new unique key, using the loop method, takes 0.0620035 seconds according to Management Studio.
Why would the amount of columns have anything to do with it?
(Did you create an Index on the TaxID column?)
Bye
A.