Добрый день!
Хотелось бы договор прочитать, для точного ответа. Но в Росреестре Вам ответили не совсем правильно.
Из вопроса я понял, что Вам ответили в регпалате (Росреестр) устно, в таком случае Вам нужно все равно сдать имеющийся договор + кадастровый паспорт квартиры на регистрацию, они обязаны принять (если нет кадастрового паспорта, то предварительно нужно поставить квартиру на кадастровый учет, для этого нужно обратиться в Крайтехинвентаризацию (или госорган по технической инвентаризации) с соответствующим заявлением).
Росреестр сначала приостановит процедуру регистрации, а потом напишет отказ в регистрации права. После получения такого отказа Вы подаете исковое заявление в суд, ссылаясь на договор и документы подтверждающие сделку купли продажи (расписка продавца о получении денег, акт приема-передачи квартиры и др.).
Исковое заявление нужно подавать о признании права собственности на квартиру, госпошлина рассчитывается от суммы инвентаризационной стоимости, которая указывается в техническом паспорте квартиры.
Если договор заверен нотариусом, думаю суд признает за Вами право собственности на квартиру, поскольку недействительность договора можно признать только в судебном порядке, поэтому Вам не нужно расстраиваться из-за неточного ответа из Росреестра и искать предыдущего хозяина.
Не забудьте оценить ответ (+ или -)