Compilation is a certainly a good idea if you're going the brute-force route. So let's first tackle that, and afterwards come up with better strategy.

Compilation

A performance pitfall when compiling functions is that sometimes the compiled function just calls the main evaluation loop, effectively gaining nothing. We can check this with CompilePrint:

Needs["CompiledFunctionTools`"]

a // CompilePrint

      (...) 
      Result = I3

 1    I3 = MainEvaluate[(...)]
 2    Return

The call to MainEvaluate is the culprit here.

So let's rewrite your function such that it does compile properly. Using Pickett's and wuyingddg suggestions, we end up with:

PerformSearch = Compile[
  {
    {startValue, _Integer}, 
    {increment,  _Integer}
  }, 
  NestWhile[
    # + increment &, 
    startValue,
    IntegerDigits[#^2][[-1 ;; 1 ;; -2]] =!= {9, 8, 7, 6, 5, 4, 3, 2, 1} &
  ]
]

Let's check if this did compile ok:

PerformSearch // CompilePrint

      (...)

 1    I4 = I0
 2    I3 = I4
 3    I7 = Square[ I3]
 4    T(I1)2 = IntegerDigits[ I7, I5]]
 5    T(I1)0 = Part[ T(I1)2, T(I1)1Span]
 6    B0 = CompareTensor[ I6, R2, T(I1)0, T(I1)3]]
 7    if[ !B0] goto 12
 8    I3 = I4
 9    I7 = I3 + I1
 10   I4 = I7
 11   goto 2
 12   Return

Ok, that looks much better. We can now perform the search, but not after we've determined the range of possible solutions:

max =   Floor @ Sqrt @ FromDigits @ Riffle[Range[9], 9] (* 138902662 *)
min = Ceiling @ Sqrt @ FromDigits @ Riffle[Range[9], 0] (* 101010102 *)

As an aside, note that max^2 is below $MaxMachineInteger on 64-bit systems. But on 32-bit it isn't, which causes PerformSearch to switch back to the uncompiled code.

Keeping Mark McClure's comment in mind, we'll cheat a bit and start from the maximum to find immediately:

result = PerformSearch[max, -1]

138901917

How much faster is this than starting from the minimum?

(result - min)/(max - result) // N

50861.5

Roughly $\mathcal{O}(10^4)$ times faster, not bad! (Starting from the mimimum takes about 30 seconds on my machine btw).

Last but not least, let's double-check if we've obtained the correct number:

result^2

19293742546274889

If you multiply result with 10, you've got your desired integer.

Non-brute-force

The approach above scanned roughly 38 million (!) integers in the worst-case scenario (starting from the minimum). Other answers to the OP's question have shown that you can and should go one better than that. Here's my take on an efficient general solution, using an iterative step-by-step process:

FindIntegerRoots[
  pattern : {(0|1|2|3|4|5|6|7|8|9|Verbatim[_]) ..},
  power_Integer: 2
] /; power > 1 := LetL[
  {
    maxRoot     = Floor[FromDigits[pattern /. Verbatim[_] -> 9]^(1/power)],
    subpatterns = pattern[[Length@pattern - # + 1;; -1]]& /@ Range@IntegerLength@maxRoot,
    RootCases   = Function[
      {digitSequences, patt},
      Select[
        digitSequences,
        And[
          # <= maxRoot,
          MatchQ[IntegerDigits[#^power, 10, Length @ patt], patt]
        ] & @ FromDigits @ # &
      ]
    ],
    InsertDigits = Replace[
      #,
      {digits___Integer} :> Sequence @@ ({#, digits} & /@ Range[0, 9]),
      {1}
    ] &
  },
  FromDigits /@ Fold[
    RootCases[InsertDigits @ #1, #2] &,
    {{}},
    subpatterns
  ] ~ RootCases ~ pattern
]

Note that this depends on Leonid's LetL function.

It is reasonably fast for the OP's question:

FindIntegerRoots @ Riffle[Range[9], _] // AbsoluteTiming

{1.930638, {138901917}}

But how efficient is it? Here's a nice graph of the amount of checks it performs in this case:

That's about 296 thousand checks in total; certainly much less than 38 million!

But the nice thing about FindIntegerRoots is that it works on any pattern, not just the OP's case:

FindIntegerRoots @ {_, 9}

{3, 7}

FindIntegerRoots @ { 1, _, 4}

{12}

FindIntegerRoots @ { 1, _, 6}

{14}

And if you're adventurous, you may even ask for roots of different powers:

FindIntegerRoots[{_, _, _, 5}, 3]

{5, 15}

There is a method by using Catch and Throw, and it gives result in about 90s. I think it can be improve a lot by Paralilize or ParallelEvaluate, but failed to finish that.

i = 10^9 + {30, 70};
isMatchQ = 
  If[IntegerDigits[#^2][[1 ;; -1 ;; 2]] ==  {1, 2, 3, 4, 5, 6, 7, 8, 
      9, 0}, Throw[#]] &;
Catch[Do[isMatchQ /@ i; i += 100, {10^9}]]

Edit

I have found a way to speed up it by ParallelTable, this is the code:

len = ((Sqrt[1.93*10^16] - 1*10^8)/40 // IntegerPart)*10;
isMatchQ = 
  If[IntegerDigits[#^2][[1 ;; -1 ;; 2]] ==  {1, 2, 3, 4, 5, 6, 7, 8, 
      9}, Throw[#]] &;
ParallelTable[n = 10^8 + {3, 7} + len*i; 
  Catch[Do[isMatchQ /@ n; n += 10, {len / 10}]], {i, 0, 
   3}] // AbsoluteTiming
(*{42.523432, {Null, Null, Null, 138901917}}*)

I divided the whole range of n which makes 10^16 <= n^2 <= 1.93*10^16 into 4 parts, the length of each part is len. And I calculate these 4 parts in 4 kernels at the same time by ParallelTable, then get the result in a much shorter time, only 42.5s. (Sorry for my poor English....)

This non-paralell strategy takes less than 4 seconds in my stone age laptop (and doesn't use the "reverse searching" trick)-

First we check for the possible 6 digits endings (after discounting the final "00" ending in the squared number):

set= 2 Position[IntegerDigits[Range[10^5 + 1, 10^6-1, 2]^2][[All, -5;; -1;; 2]], {7,8,9}]+ 10^5 - 1; 

Then we complete the whole set of numbers to check by adding all the possible "heads" between the max and min:

fullSet = Total[Tuples[{Range[101, 138] 10^6, Flatten@set}], {2}];

And then a quick search gets our number:

Cases[IntegerDigits[fullSet^2], {1, _, 2, _, 3, _, 4, _, 5, _,  6, _, 7, _, 8, _, 9}]

(*{{1, 9, 2, 9, 3, 7, 4, 2, 5, 4, 6, 2, 7, 4, 8, 8, 9}}*)

adding the final zeroes:

(* 1929374254627488900 *)

Edit

We can still cut the time in half if we see that the number should end in 3 or 7 for its square to end in 9:

set = Join[10 (Position[IntegerDigits[Range[10^5 + #, 10^6, 10]^2][[All, -5 ;; -1 ;; 2]], 
                       {7, 8, 9}] - 1) + # & /@ {3, 7}] + 10^5;
fullSet = Total[Tuples[{Range[101, 138] 10^6, Flatten@set}], {2}];
Cases[IntegerDigits[fullSet^2], {1, _, 2, _, 3, _, 4, _, 5, _,  6, _, 7, _, 8, _, 9}]

Most PE problems are designed such that any computing system will buckle under the teraflops usually required to brute force a solution. Not so many flops required for this problem, but some experiments can dramatically reduce the number of tests required.

The minimum possible square is 1020304050607080900, and the maximum square is 1929394959697989990, corresponding to a range of integers $n$ from 1010101010 to 1389026623. Apparently, there are about 380 million integers to test. However, the only possible square ending in 0 must end in 00. So the last three digits of the square are ...900. Therefore, the integers $n$ to be squared must all end in either 30 or 70, and the number of such integers to test is now only about 7.6 million.

The required integer is unique, according to the problem statement, so a simple, direct use of ParallelSum with Boole is possible. Avoid MatchQ as @Pickett suggests.

AbsoluteTiming[
   ParallelSum[
      n*Boole[IntegerDigits[n^2][[;; ;; 2]] == {1,2,3,4,5,6,7,8,9,0}],
      {n, 1010101030, 1390000000, 100}] + 
   ParallelSum[
      n*Boole[IntegerDigits[n^2][[;; ;; 2]] == {1,2,3,4,5,6,7,8,9,0}],
      {n, 1010101070, 1390000000, 100}]]
(* {5.915985, 1389019170} *)

Further investigation shows that there are only three possible 5-digit endings for the required square: {{8,0,9,0,0},{8,4,9,0,0},{8,8,9,0,0}}. The corresponding 5-digit integers whose squares have these endings are of the form $i+2500k$, where $i=\{10530,11970,10430,12070,10830,11670\}$, and $k=0,1,2,...35$. The beginning 5 digits of the integer range from $j=10101$ to $j=13890$. Thus, integers $n$ of the form $n=100000*j+i+2500k$ have squares with the required 8_ 9_ 0 ending. Now there are only about 821 thousand integers $n$ to test. Approximately 460 times fewer tests than a direct brute force approach.

AbsoluteTiming[
   ParallelSum[
      (100000 j + i + 2500 k) *
         Boole[IntegerDigits[(100000j+i+2500k)^2][[;; ;; 2]] == {1,2,3,4,5,6,7,8,9,0}],
      {j, 10101, 13890},
      {k, 0, 35},
      {i, {10530, 11970, 10430, 12070, 10830, 11670}}]]
(* {1.002618, 1389019170} *)

But nothing beats counting down from the maximum as @MarkMcClure comments.

Here's a slight improvement of @wuyingddg's Catch&Throw method. The key point is to make Throw working inside ParallelDo using the method mentioned in this post:

SetSharedFunction[pThrow];
pThrow[expr_] := Throw[expr]
isMatchQ = 
  If[IntegerDigits[#^2][[1 ;; -1 ;; 2]] == {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}, pThrow[#]] &;
Catch[ParallelDo[
   isMatchQ /@ (i + {30, 70}), {i, 10^9, Sqrt[193 10^16], 100}]] // AbsoluteTiming