всё

тут видятся такие варианты:
1. если договор (сделка) регистрировались в БТИ, то у них. я, если честно, не в курсе передавали ли БТИ информацию в Росреестр.
2. если сделка была нотариальная, то у нотариуса.
3. найти продавца из 1996 года, может у него что есть.
4. оригинал искать тщательнейшим образом.
5. через суд признавать право.

1. Получаете дубликат договора у нотариуса, который удостоверял сделку.
2. Получаете в БТИ документ, подтверждающий регистрацию договора - заключение о соответствии правоустанавливающего документа данным правовой регистрации.

Эти два документа заменяют подлинник утерянного договора.

Ну это смотря какого года договор. Уже некоторое время не обязательно удостоверять сделку у нотариуса.

У ТС договор был очень древний, "доюстиционный", удостоверенный нотариусом и зарегистрированный в БТИ.