I can show the probability that Waldo returns to 0 is 1. Waldo's wanderings map to an integer grid in the plane as follows. Let (X_t,Y_t) be the cumulative sums of the length 1 and length 2 steps respectively taken by Waldo through time t. By looking only at even t, we get the ordinary random walk in the plane, which returns to the origin (0,0) with probability 1. In fact, landing at (2n, n) for any n will land Waldo on top of his keys too. There's no need to look at odd t.

Similar considerations apply for step sizes of arbitrary (fixed) size.