Check for any filtering on your contacts list, try changing your view to make sure you are seeing all of your contacts.
You can try closing outlook, going to start – run and typing outlook /cleanviews. This will reset your views to default to rule out the views being an issue. There are more switches you can try here. If this is a POP3 account you can try repairing the .pst with scanpst also. If this is an exchange account, please say so. Thanks!