The ordering of two-dimensional Ag islands embedded in the Pt(111) surface layer has been investigated using He-atom scattering and scanning tunneling microscopy. At lower Ag coverage the embedded islands consist of compact clusters (disks) arranged into a short-range ordered two-dimensional array. At higher coverage the Ag islands have an elongated shape leading to a ''labyrinthine'' pattern of regularly spaced meandering stripes. As the temperature is increased, both the disk and stripe arrays of embedded Ag clusters transform reversibly into a disordered 2D Ag-Pt mixture. The observed behavior is explained in terms of strain-induced long-range interactions.