The realization of spin-based devices requires high density, ordered arrays of magnetic materials with a high degree of spin polarization at surfaces. We have synthesized, for the first time, highly spin polarized complex magnetic oxide nanostructures embedded in a paramagnetic matrix by electron beam lithography and ion implantation. Imaging the magnetic domains with X-ray photoemission electron microscopy and magnetic force microscopy reveals a delicate balance between magnetocrystalline, magnetoelastic, and magnetostatic energies that can be tuned by the choice of SrTiO3 substrate orientation, film thickness, island size, and island shape.