you could index your nulls with a function-based index, but if the ratio of deletes to actives get's high then it would be time to throw them in a history table i guess. Kind of a hybrid solution.

As soon as the possibility of "undeleting" a record get's raised as a business requirement, that would be time for me to say "well, you don't want to delete them at all then, do you?" The requirement kind of shifts to providing status flags for records, which is something more intuitively understood i think.

To my mind, "delete" as a business requirement means "gone forever". You want it back, you create it again, you don't "undelete"