I really wish people would stop talking about MD5 already. It is almost never the answer. On a modern CPU you get HW accelerated SHA-256, it will always be much faster than your best software MD5. If your SHA-256 hash is too long, chop it up, it will still be better than MD5 for the same bit length.
In general I agree with you- there aren't many cases to consider using MD5 anymore, but in this instance it will work well enough (still insanely fast) on new and old machines alike. If you know SHA-256 will be more optimal for your target hardware, by all means go for it. Some of the physical servers I run are a few years old and are slow at SHA, so the hash key calculations would get expensive quickly.
Shard hash keys aren't sensitive to the weaknesses of MD5, so there isn't an inherent problem, which is why I suggested it. It's really only an implementation detail and immaterial to the underlying question I was hoping to address.
