Exchange 5.5/Custom Recipient Problem

I am having problems sending email out to my custom recipients. I have Exchange 5.5 SP3 running and emails being sent out to custom recipients in the address book are being returned as undeliverable “the recipients name is not recognized.” It doesn’t matter what internet address I assign, it still does not work. It does not even attempt to deliver outside my network. It querys the Exchange server for the address then bounces the undeliverable message back to the client. Is there somethingI am overlooking here? My Outlook Clients can send to outside email addresses, as long as the custom recipient is not in the address book.