Due to its potential application in magnetic recording and sensing technologies, the anisotropic magnetoresistance (AMR) effect has attracted lasting attention. Despite the long history, AMR effect has not been fully understood especially in the unconventional materials, such as perovskite manganites. Here, we report an unusual AMR effect in the charge-orbital ordered (COO) Nd0.5Sr0.5MnO3 polycrystals, which is observed when the magnetic field rotates in the plane that is perpendicular to the current (out-of-plane AMR). Despite being a polycrystalline sample where no anisotropy is expected, the resistivity shows a large irreversible drop with rotating magnetic field. A model has been proposed based on anisotropic magnetic field induced the melting of COO phase to explain the unusual out-of-plane AMR successfully. Our results demonstrate a new way for understanding the close relationship between phase separation and AMR effect in COO manganites.