Limit superior of $\sum_{j=1}^n X_j$ with $\mathbf{P}[X_j = 1] = \mathbf{P}[X_j = -1] = 0.5$

You are on a good start. We already know that $\mathbb{P} (A) \in \{0, 1\}$, but how do we decide which one?

First remark: a sequence $(X_n)$ is in $A^c$ if and only if its sum is bounded from above, i.e., if and only if there exists $N \in \mathbb{N}$ such that $S_n \leq N$ for all $n$.

Now, let's use the symmetry of the random walk. The map $(X_n)_{n \in \mathbb{N}} \mapsto (-X_n)_{n \in \mathbb{N}}$ preserve the distribution of the sequence of random variables (they are still independent, and have the same distribution for all $n$). Hence,

$$\mathbb{P} (\limsup_n S_n = + \infty) = \mathbb{P} (\limsup_n -S_n = + \infty) = \mathbb{P} (\liminf_n S_n = - \infty).$$

If I write $B$ the event $\{\liminf_n S_n = - \infty\}$, then $\mathbb{P} (A) = \mathbb{P} (B) \in \{0, 1\}$. Let $C$ be the complement of $A \cup B$. Then $C$ is exactly the set of sequences which are bounded from above and from below, so the set of bounded sequences. Hence,

$$C = \bigcup_{N \in \mathbb{N}} C_N,$$

where $C_N = \{|S_n| \leq N \ \forall n \in \mathbb{N} \}.$

I sum up. If $\mathbb{P} (C) = 0$, then $\mathbb{P} (A \cup B) = 1$. But $A$ and $B$ have the same probability, so $\mathbb{P} (A) \geq 1/2$. Since $\mathbb{P} (A) \in \{0, 1\}$, this forces $\mathbb{P} (A) = 1$. Hence, I only need to prove that $\mathbb{P} (C) = 0$, that is, that each $C_N$ has measure $0$.

Fix $N$. Remark that if there is a sequence of $2N+1$ elements of $(X_n)$ which have the same sign, then the sequence cannot belong to $C_N$.

For $k \geq 0$, let $D_k$ be the event $\{(X_{(2N+1)k}, X_{(2N+1)k+1}, \cdots, X_{(2N+1)k+2N} \text{ all have the same sign} \}$. Then all the $(D_k)$ are independent, and $\mathbb{P} (D_k) = 2^{-2N - 1}$ for all $k$. By Borel-Cantelli's lemma, almost surely, a sequence will lie in an infinity of $D_k$'s, and thus in at least one of them. Since being in any $D_k$ precludes being in $C_N$, this yields $\mathbb{P} (C_N) = 0$.

Since this is true for all $N$, we get $\mathbb{P} (C) = 0$, and from there, $\mathbb{P} (A) = 1$.