You said:
In my case I only have to deal with maybe 50 names but each has a Home/Office/Cell/Fax/Ofc Extension# etc and it is tiring to have to look them all up on their email signatures or deal with the MS Office Contact program just to get a phone number every time it is needed.
The "paper sheet" hard-copy version tends to "migrate south". (ie: the Round File Area) or.. maybe migrates to other desks!
I would not complain if there was room for an email address on each person as well.

Simply use Treepad. A template is attached. It is "Treepad Lite" that you need. It doesnt cost you anything. You can download Treepad Lite free.
www.freebyte.com, If any one user changes any parameter such as Cell/Fax etc. simply update your master copy publish it using same Treepad Lite using Export > Subtree > HTML function and store that HTML in intranet.

All 50 users can view how they appear in your address book using the intranet. Should they want any change, they can call you to have their entries updated.
Attached is treepad template Office Phone Book.hjt in a zip file.
.hjt is the Treepad format.
This format is the best format for you because there is another format called .tpd. That comes of use if you are using Treepad Business Version.
In the template, I have entered 10 users, simply copy and paste from subtree to subtree you will have 50 users in 5 times copy-paste.

Attachment :
UNZIP the attachment and open the .hjt file using treepad lite.
Treepad lite can be downloaded from www.freebyte.com