>Replace the key with a unique/random string when marking it as deleted.

Ok, this is old hat.

I have a non-PK that I want to ensure is unique. The Recycling method won't work in this archeticture. If a value is deleted, and then readded, I don't want this to cause a uniquness error because of a Canidate key or something. So the two best methods I can think of are Using a Canidate Index with a filter that only applies to Not Deleted for the uniquness and also maintaining a Regular index for Rushmore's use OR what Ken says above.

I've used both, but can anyone tell me which is better for a reason (and not just theoritcal reasons either). Or a differnet method? I always have trouble deciding.