Asterisk / Elastix Address Book and Call Recording

I am trying to build a small asterisk based PBX using Elastix. It’ll be having 4 FXO (2 nos.no ISDN, normal analog POTS, 2 nos. GSM connections using a GSM Terminal) and 4 FXS (2 IP Phones and 2 Android SIP Client).

I am confused about the following two issues and need your help:

1. I need to record all Incoming / Outgoing Calls along with their Caller Ids, Is any special hardware needed ?

2. I have about 5000-6000 contacts which I want to show up on my IP Phones menu, so that users can dial by selecting / searching the name / company. How can this be implemented and which is the most cost effective IP-Phone to purchase for contacts list of this size.

Thanks a lot for your time