MySQL unique index only if column has specific value
I had a similar question, and have a way to make it work, so if you don't mind the kludge, here it is:

Since MySQL allows multiple NULL values on a unique index, you can use NULL to indicate "deleted" and non-NULL value (42?) to indicated "not deleted". 

You would then create a composite unique index on [slug, deleted]. 

The table would look like this:

slug   deleted
abcd   42    # This record is marked as not-deleted
abcd   NULL  # This record is marked as deleted
abcd   NULL  # This record is marked as deleted
xyz    42
xyz    NULL


If using non-NULL to signify "not deleted" seems a bit iffy, so if you can, you could reverse the values and change the column name to "available" or something? :

slug   available
abcd   42    # This record is marked as available
abcd   NULL  # This record is marked as not-available  
abcd   NULL  # This record is marked as not-available
xyz    42
xyz    NULL


Hope that helps