Actually, you usually have both - you have mechanical accelerometers (they measure rate of acceleration and its direction) and sometimes also gyroscopes (they measure the rate & direction of rotation) but you also have the magnetic compass that measures orientation in a magnetic field. It is right that you can go an inertial compass with the help of the two above mentioned sensors, but it would accumulate errors over time and would require periodic calibration from an outside source ("north is this way!" to work correctly).

On the other hand, some compass using applications tell you to rotate the device a few times before use to improve compass accuracy. So my theory is that the compass probably measures magnetic field changes and not absolute values, so strong magnets in a constant distance from the sensors might be be an issue as long the sensor can pick up the magnetic filed changes when the device rotates.

But that's just my guess - a more detailed analysis from someone with actual relevant engineering background would be welcome!