Так задумано. Если не стоит галка "Автоматически удалять локальные контакты, отсутствующие в списке друзей", то контакт-лист = френдлист + собеседники 200 последних диалогов.
Почему у локального контакта-не друга нет пункта "Добавить в друзья" я сказать не могу - мало информации. Нужно подробное описание того, как удаляли, передергивали ли протокол после этого, нетлог и т.д.