Присоединяюсь к советам взять нокию.
Хочется предупредить, что глюки с дублированием неизбежны, так как адресная книга у S40 убогая.
Судя по табличке
www.google.com/mobile/sync/ Целиться надо на Symbian в продаже еще имеются телефоны на этой платформе, например С5. За пять тысяч можно взять и андроид :)