Great discussion so far. I wanted to chime back in and say that I agree with the recommendations for using SHA-1, but by using the ID plus the Hash to identify records MD5 works very well and has little to no chance for producing a collision.
Either way works fine, and my code should be able to modified very easily to produce a SHA-1 hash as well.
Here's a revised CreateHash function that should work for SHA-1 hashes (haven't tested just going off memory).
Public Shared Function CreateHash(ByVal data As String) As String
Dim dataToHash As Byte() = (New UnicodeEncoding()).GetBytes(data)
Dim sha As New SHA1CryptoServiceProvider()
Dim hashedData As Byte() = sha.ComputeHash(dataToHash)
Dim s As String = Convert.ToBase64String(hashedData, Base64FormattingOptions.None)