We have carried out a high statistics (2 Billion events) search for ultra-high energy gamma-ray emission from the X-ray binary sources Cygnus X-3 and Hercules X-1. Using data taken with the CASA-MIA detector over a five year period (1990-1995), we find no evidence for steady emission from either source at energies above 115 TeV. The derived upper limits on such emission are more than two orders of magnitude lower than earlier claimed detections. We also find no evidence for neutral particle or gamma-ray emission from either source on time scales of one day and 0.5 hr. For Cygnus X-3, there is no evidence for emission correlated with the 4.8 hr X-ray periodicity or with the occurrence of large radio flares. Unless one postulates that these sources were very active earlier and are now dormant, the limits presented here put into question the earlier results, and highlight the difficulties that possible future experiments will have in detecting gamma-ray signals at ultra-high energies.