Office Communicator relies on Service Location (SRV) records in DNS for auto-configuration. Frequently you can't create the external DNS record yourself so you need to ask your ISP or DNS provider to do it for you.
So if the service provider is swearing black and blue that the records have been created correctly but your external client is not finding the server checking your DNS configuration is a great place to start.
There is a tool in the OCS Resource Kit called SRVLookup that will fetch and parse the SRV records for a given domain for your review.
However if you are out and about and don't have the resource kit handy there is a quick and dirty way to check SRV records using NSLookup.exe in interactive mode from the command line. The screenshot below shows the sequence of commands needed to test for the _sip._tcp SRV record for the mycompany.com domain. Click for a bigger view....