However ... the absolute max approved altitude may be impractical for test for a variety of reasons, including things like the weight of an instrumented test aircraft compared to the minimum production weight, and what that implied for altitude capability. Therefore, there is some latitude in practice, provided you can justify that the altitude you have tested to is adequate to address the case for the maximum altitude. (AC25-7C - or any other AC for that matter - is, after all, advisory and doesn't have the full force of regulation)
And to the second, there are cases where compressibility actually affects the stall behaviour at low altitude as well, although the mechanisms can be a bit complex.