У вас есть несколько вариантов; как вы говорите, изолированное хранилище является одним из них. Вы также можете использовать функцию инфраструктуры пользовательских настроек и сохранить данные в виде большого двоичного объекта или в формате XML.
Вы также можете взглянуть на SqlCompact для очень легкой в работе базы данных. Затем вы можете сохранить все пользовательские контакты в одной базе данных, которая может жить, например, в том же каталоге, что и приложение; Вы можете легко использовать что-то вроде EF4 для своего DAL.
Хотя это может быть немного больше усилий, так как кажется, что вы находитесь на 99% пути с вашей текущей архитектурой.