Agreed... the ball is not in play until it leaves the penalty area. And a ball _off_ the field of play is... well... not in play.
Therefore, the play has not restarted, so... retake. Same would apply to an IFK or DFK taken within the penalty area by the "defending" team.
It's much like a throw-in. If the thrown ball does not cross onto/over the touchline, then the throw is retaken, as the ball never came into play.
Note that the 2012 FIFA LotG Quiz has the answer as a corner if it goes out of the PA onto the field of play then crosses the goal line, and a retake if it crosses the goal line before leaving the PA onto the field of play.