What you are looking for is a database. Excel, which is a spreadsheet program, can function as a database, but you usually don't get the fun front end. The more sophisticated db programs in common use are Access, which is hardly intuitive, and Corel/Borland Paradox, which has a daunting little learning curve, but is pretty doable for a self starter. Take a look at the Paradox group here and ask them how you would do that.
The advantage of these programs is that you or a tech person can alter them and refine them to your needs as your business grows. You can also take any business contact program (Act! for instance) and alter it with it's own interface to suit your ends.
Note that Paradox comes only boxed with the Corel Office Pro suite, which has some other useful tools, but you can get that more cheaply if you do some internet searching. The Corel suite lets you get by without a tech, if you are willing to put in the time, but you may find professional help well worth what it costs, especially if it goes over a network.
Two more programs which you can tailor (or have tailored) are Filemaker Pro for Windows and Delphi, neither of which I know. If you search ZD net, you will find a couple of other off market versions which are reportedly quite good.
I have heard that Borland, the company which created Paradox, may cease to develop the engine, which means that it may at some point become obsolete. Something more to ask a tech.
By the way, if you choose to start with a pre formated contact software, you can always export your data to another program later if you find the software does not fill your needs.
Have fun. (I think a lot of the people who hang out in the Paradox section are consultants, so I imagine you wouldn't have much trouble finding someone to do your job for you.)