База данных или XML-файл для приложения на Windows Phone?

Вы сами уже перечислили все доводы в пользу базы данных и против XML. Большой объем данных — XML не имеет индексов, не имеет типизации данных и имеет большой оверхед на разметку, что приведет к долгому считыванию данных (а еще учтите, что телефон — вещь в ресурсах очень ограниченная, а ожидание раздражает пользователя в большей степени, чем в случае компа). Плюс XML это лишь формат, функции сортировки, выборки/фильтрации, объединения разных представлений придется вам разрабатывать самостоятельно.
В случае с БД все эти вопросы решены.
С точки зрения выборанного паттерна — нет абсолютно никакой разницы, у вас в любом случае есть некий источник данных, который отвечает за хранение, предоставление, обновление в хранилище тех самых данных. И не важно, будет этим хранилищем XML или SQLite-база, или, может, что-то еще.
И полагаю, что у микрософта для WinPhone должно быть что-то подобное эппловскому CoreData. А если так, то нужно очень хорошо подумать, прежде чем отказываться от такого фреймворка для хранения данных.