Какую программу вы посоветуйте для малого бизнеса для хранения записей клиентов(имя,тел.номер, адрес)?

Я бы посоветовал не замарачиваться особо и использовать excel
быстро и просто, поиск есть, малый бизнес - количество клиентов не запредельное.

Сейчас существуют веб версии электронных таблиц, как от microsoft http://office.microsoft.com/en-us/web-apps/ или так https://skydrive.live.com/
так и от google https://docs.google.com
все что нужно зарегистрироваться, использование этих продуктов бесплатно и легально

Access - для таких дел и существует.

notepad (на полном серьезе)

Exel 100%  Сам использую и очень доволен.

я заказала у одной фирмы сайт и атм  в нутри есть база данных. ну мне очень удобно.