Solving a Rubik's cube via a series of randomly selected (quarter-turn) Singmaster moves

I think the expected time for stumbling across the solution is roughly proportional to the number of configurations. The process you describe is walking randomly on a Cayley graph. The limiting distribution is uniform, so after a large number of steps you will be in approximately a random place and the chance of that being the solution is the reciprocal of the number of vertices (i.e. the number of configurations). If someone expert in rapid mixing of Markov chains comes along, they will tell us if this argument can be made rigorous.

ADDED: This much is certain: Say $N$ is the number of configurations. If you start at a random configuration, then the probability of being at the solution configuration after $i$ steps is exactly $1/N$ for every $i$. However these are not independent events. The expected number of solutions seen in the first $N$ steps is exactly 1, but it does not follow that the expected wait for the first solution is $N$.