вариантов объяснения тысячи...
самое простое сбросить телефон, а то и оба, к заводским настройкам и заново попробовать.
Ессно это не самое лучшее решение, но самое надежное. Просто вариантов и в самом деле много - не зная моделей телефонов, типа отправляемого сообщения и так далее сказать сложно.
Приведу пример - имя человека, которому отправляют в записной книжке дважды. При чем каждый раз - разный номер. Человек отправляет на номер человека, выбирая номер из записной книжки - сообщение отправляется и доставляется другому человеку, но на записанный в записной книжке номер. После этого человек заходит в записную книжку (проверить номер) и проверяет - правильно ли сохранен номер, но выбирает при этом вторую запись - где номер сохранен правильно.
Сначала попробуйте вводить номер полностью цифрами в международном формате (+49), а не из записной книжки.
Есть и другие варианты - есть телефоны, которые не показывают входящие сообщения, если они пришли "завтра" - то есть дата на телефоне установлена неправильно - поэтому сообщения как бы в будущем. Звучит нелепо - но блекберри действуют именно так.
Да вообще - вариантов куча.