As many people (including me) have pointed out, John McCain's reputation for "straight talk" is highly exaggerated. Indeed, he's changed his views so many times it's hard to know what he thinks. At the same time, however, his voting record is more conservative than his "maverick" reputation suggests.
A friend points out that the book Ideology and Congress by 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):
Given the pace of events, it would be possible for the major dimension to show rapid legislator shifts. In our dynamic model, very rapid shifts are foreclosed by our imposition of the restriction that individual movement can only be linear in time. This restriction fails to capture a few cases. For example, John McCain (R-AZ) started as a conservative, became a moderate after losing the Republican nomination to George Bush in 2000, and recently reemerged as very conservative. McCain is an exception...
The fact that he's largely gotten away with this double evolution should be seen as an amazing political accomplishment. But I think the political environment is so favorable to Democrats that the media will eventually start hammering him. The questions about his dalliance with John Kerry in 2004 are already starting...