Как избавиться от слежки СМС?
Ну, начать надо с бессмертной фразы "какие ваши доказательства?" Ну то есть, пусть продемонстрирует, что кто-то может что-то читать, а не просто блаблакать.
Разумеется, такие возможности есть, причем вполне себе легитимные. Например "МТС.Поиск" - сервис такой. В базовой версии отслеживает передвижение по городу, при установке агента на телефон - позволяет полностью удалено управлять им (в том числе прослушивать окружение через микрофон телефона). Для подключения к сервису достаточно бросить незаблокированный телефон - придет смс с запросом на согласие, ответить да - и вуаля :)
Как проверить? Посмотреть, нет ли на телефоне агента. Если агента вроде нет, а доступ есть - сделать полный сброс телефона. Если не было рута, этого будет достаточно. Если рут был - лучше его перешить.
Во 1. Он и она живут в разных городах, поэтому он мог сделать это, опять же, только удалённым образом.Смс (чужие), не имея в руках телефона жертвы, можно читать 3 способами: 
1) Из софта оператора связи, имея соответствующий доступ (ну или нужных людей с ним)
2) Перехват смс аппаратными средствами, емнип во многих регионах они до сих пор шлются бродкастом через нешифрованные каналы
3) Шпионский софт на целевом аппарате. 

С первыми 2 скорее всего сделать практически ничего нельзя, кроме как обратиться в органы, но без доказательств они тоже нифига сделать не смогут. Хотя во втором случае вроде как аппарат имеет свойство палиться при подключении к сети (но это не точно и хз как силовики с этим будут разбираться), а в первом факт незаконного доступа хрен отследишь.

по 3 пункту уже сказали - сброс или ручной поиск подозрительного софта.