Keith Poole and Howard Rosenthal, the two authors of the most widely used estimates of the ideal points of members of Congress, can help square the circle on McCain to some extent.
On pages 2-3, they note that their algorithm tends to place McCain as highly conservative but that his voting record is especially inconsistent, causing the predictive accuracy of their estimates to be the lowest of all the members of the Senate during the sessions in which he has served (i.e. "the worst fitting"):
There are, to be sure, occasional mavericks in Congress... John McCain (R-AZ), normally one of the very most conservative members of the Senate, has been the worst fitting member of the Senate in each of his eight Senates, most notably the 103rd (2001-02), where he frequently voted with the Democrats, perhaps in pique over losing the race for the presidential nomination in 2000.
They later note that the rapid evolution of McCain's views is abnormal and not fully accounted for by their statistical model, which assumes members don't bounce around so much (p. 93)...
Is this just coincidence? Is being an outlier a smart way to get national attention? My guess is that being an outlier is just a high-variance strategy that happened to pay off.