@markr,
Assuming Z > 2^64 (otherwise it's trivial) and A^x >= B^y, then
Z > A^x >= (Z - 2^64)/2
If Z is quite large, for each A, there is only one x that satisfies the above inequality (although for A=2, there are potentially two values for x). That narrows the search, but you still have to check 2^32 values for A, and for each A, you need to do a similar thing to find a B^y that gets you within 2^64 of Z.
That's the best I can do.