Вряд ли оффшорные компании станут закон РФ соблюдать. Но, если потребуется, технически выход мне видится в таком направлении.
Компания арендует сервер (или часть его ресурсов) на территории РФ и ведет базу персональных данных, хранимую действительно только там. Сервер обслуживает запросы компании по проверке (сравнению) присылаемых компанией данных с хранимыми в базе. Например, при введении логина и пароля запрос авторизации отправляется на сервер в РФ, сервер отвечает Да/Нет. Возможна и выдача с сервера персональных данных, но только по одному человеку, ни в коем случае не по всем. Естественно, с протоколированием всех запросов и ответов.
Возможно, здесь появятся сертифицированные государством программы, обеспечивающие исполнение законодательства РФ. В частности, допуская лишь запросы к базе из заданного списка допустимых. Ведь опыт ведения персональных БД в России имеется давно, и там всегда было разграничение доступа.