Do you need really the precise asymptotics of that probability? Or a "reasonably good" bound (with fast decay in $n$) will do?

No, on step (4) you only use the Optional Stopping Theorem and the boundedness of jumps. Just think how would you solve the Gambler's Ruin Problem for equally strong players using the fact that the one-dimensional SRW is a martingale; that argument easily generalizes to any martingale with bounded jumps (you'll obtain 2 inequalities instead of 1 equality, but that's still OK).

Just complementing: $\bar{\mu}_1(t)$ and $\underline{\mu}_2(t)$ are essentially the two displays in my answer above, with $t=\|x\|$.

Yes, that bound may not be so useful, since if $x$ is far away from $x_0$, then you're not likely to go to $x_0$ on the way from $x$ to $x$. By my experience in constructing Lyapunov functions for complex chains, I would suggest it's kind of an art: you try one function, if it doesn't work, you try to tweak it, etc. You may want to look at our book, ime.unicamp.br/~popov/book_lyapunov.pdf (published by C.U.P.)

No, I don't think you can obtain the Lyapunov function only from $\pi$. At least, don't think there is any "general" way to do this. The "canonical" Lyapunov function in the positive recurrent regime is $f(x)=E_x$(time to reach $x_0$), where $x_0$ is some fixed site, and this is not much related to $\pi$.

@anthony-quas: no, the LIL doesn't imply that. It implies that the trajectory is unlikely to remain in $\{(t,y): t\in[0,n], |y|\leq c\sqrt{t}\}$; here, the question is if it can remain in $\{(t,y): t\in[0,n], |y|\leq c\sqrt{n}\}$

You're welcome! And good luck with the paper!

"if we consider the states as a tuple of queue size and of a binary variable that indicates if server is maintained" - here we can kind of "join" all the maintenance states into one (as indicated in the response). But you can alsouse the Lyapunov function $f(1,n)=n$, $f(0,n)=n+c$ for suitable $c>0$ ($1$ means server works, $0$ means it's under maintenance).