А можешь текст их письма здесь выложить? Ибо:
1. Они как минимум должны были с чего-то решить, что данные не верны (Телефон левый вписывал? Сами данные - правдоподобные или от балды?)
2. Насколько мне известно, копия паспорта не подлежит нотариальному заверению. А для подтверждения данных регистратору достаточно скана паспорта, который тебе за полчаса и три доллара нарисуют на хакере.
Так что может быть не всё ещё потеряно. Скинь в тему полный текст переписки, попробуем мозговой штурм устроить.