In order to qualify N:N relationships, you could use the connexion entity in Dynamics CRM 2011.
The connection form displays a start date and an end date that you could use.
Of course, using this new implementation implies data migration to convert your existing N:N relationships to connections. Hopefully, you can import Connection records using Excel import.