During efforts to crystallize the enzyme 2,4-dihydroxyacetophenone dioxygenase (DAD) from Alcaligenes sp. 4HAP, a small number of strongly diffracting protein crystals were obtained after two years of crystal growth in one condition. The crystals diffracted synchrotron radiation to almost 1.0 Å resolution and were, until recently, assumed to be formed by the DAD protein. However, when another crystal form of this enzyme was eventually solved at lower resolution, molecular replacement using this new structure as the search model did not give a convincing solution with the original atomic resolution data set. Hence, it was considered that these crystals might have arisen from a protein impurity, although molecular replacement using the structures of common crystallization contaminants as search models again failed. A script to perform molecular replacement using MOLREP in which the first chain of every structure in the PDB was used as a search model was run on a multi-core cluster. This identified a number of prokaryotic phosphate-binding proteins as scoring highly in the MOLREP peak lists. Calculation of an electron-density map at 1.1 Å resolution based on the solution obtained with PDB entry 2q9t allowed most of the amino acids to be identified visually and built into the model. A BLAST search then indicated that the molecule was most probably a phosphate-binding protein from Stenotrophomonas maltophilia (UniProt ID B4SL31; gene ID Smal_2208), and fitting of the corresponding sequence to the atomic resolution map fully corroborated this. Proteins in this family have been linked to the virulence of antibiotic-resistant strains of pathogenic bacteria and with biofilm formation. The structure of the S. maltophilia protein has been refined to an R factor of 10.15% and an Rfree of 12.46% at 1.1 Å resolution. The molecule adopts the type II periplasmic binding protein (PBP) fold with a number of extensively elaborated loop regions. A fully dehydrated phosphate anion is bound tightly between the two domains of the protein and interacts with conserved residues and a number of helix dipoles.