I'd use a local variable and a WHILE loop to avoid the recursive function call:

public function generateToken($length = 5)
{
    $token_exists = true;
    while ($token_exists) {
        $token = strtoupper(substr(md5(rand()), 0, $length));
        $token_exists = $this->tokenExistsAlready();
    }
    return $token;
}