WEEELL there's deleting and deleting . . . e.g. we keep a client's address history (kind of audit trail), old addresses are never un-virtually-deleted but we still need them.

I use the end-date method for this and other m2m tables. In the cases I have looked at over the years, the lack of an efficient index on end-date did not, in practice, slow things down. Either I retrieve 5 rows (using another index) and only display 1 of them - OK, I'm wasting milliseconds. Or I'm in a FTS regime where jugling with indexes and selecting on NULL or NOT NULL did not make any difference - sometimes FTS is the best way. There is a middle ground where this WILL make a difference, but I don't think I've been there.