Among the challenges related to rechargeable magnesium batteries (RMBs) still not resolved are positive electrode materials with sufficient charge storage and rate capability as well as stability and raw material resources. Out of the materials proposed and studied so far, vanadium oxides stand out for these requirements, but significant further improvements are expected and required. They will be based on new materials and an improved understanding of their mode of operation. This report provides a critical review focused on this material, which is embedded in a brief overview on the general subject. It starts with the main strategic ways to design layered vanadium oxides cathodes for RMBs. Taking these examples in more detail, the typical issues and challenges often missed in broader overviews and reviews are discussed. In particular, issues related to the electrochemistry of intercalation processes in layered vanadium oxides; advantageous strategies for the development of vanadium oxide composite cathodes; their mechanism in aqueous, "wet", and dry non-aqueous aprotic systems; and the possibility of co-intercalation processes involving protons and magnesium ions are considered. The perspectives for future development of vanadium oxide-based cathode materials are finally discussed and summarized.