Client database help

Hi there,
I have a client who runs a small business that asked me to find some inexpensive software that will do the following:

client based program required that will auto look up cust by postal code , address , telephone # or name

also will notify time for service month only required . the 1st day of each month program will need to print out all that months customers along with history of past jobs
warranty ect...

needs to be accessible for info updates as well

will needto be set up for calander for years in advance as some cust services are booked for up to 5 years and multiple times during any calander year.
Any and all input is welcome.
Thanks :?)

Roy