In this work we present a novel conservative, semi-implicit, finite-volume scheme, designed for the numerical simulation of magnetically-dominated plasma rapidly evolving from a near-equilibrium state into a time-dependent compressible regime. The proposed scheme utilises a well-studied flux vector splitting approach, where the ideal magnetohydrodynamic (MHD) system is partitioned into two sub-systems, one containing all the advective terms and the other containing the rest of the terms, including not only the gas pressure but also magnetic pressure terms. The former is discretised explicitly as part of a standard finite-volume update, while the latter is treated implicitly by means of a nested Picard algorithm. As a result, the algorithm is constrained only by a mild velocity CFL stability condition, rendering it highly suitable for low Mach number flows in both gas and magnetic pressure dominated conditions, and for the incompressible limit of the MHD equations. The visco-resistive dissipative terms are also treated implicitly so that the numerical stability of the algorithm remains dependent only on the fluid velocity, maintaining its efficiency even for visco-resistive dominated problems. The divergence constraint of the magnetic field is handled through either staggered or unstaggered adaptations of the constrained transport methodology, which are both shown to preserve the divergence error up to machine precision levels. The algorithm is validated thoroughly by means of several benchmark problems for high and low Mach number flows, as well as multiple visco-resistive test cases. The scheme is found to perform well for both regimes, providing accurate and computationally efficient results in low Mach number flows in both gas and magnetic pressure dominated scenarios, while also demonstrating excellent shock-capturing capacity. A novel test case is finally introduced to truly demonstrate the all Mach number capabilities of the proposed scheme.