Okay, so here is my answer that I promised. I initially thought it would be quickish, but my answer has become quite large, so at the begining, I state my general results first, and leave the gory details down the bottom for those who want to see it.
I must thank @terry felkrow for this fascinating question - if I could give you +10 I would! This basically is a prime example of the slickness and elegance of Bayesian and Maximum Entropy methods. I have had much fun working it out!
SUMMARY
Exact result
$$Pr(\theta \in (0,S)|F_{obs},T_U,T_D)=1-\frac{T_U}{T_U+T_D}\Bigg(\frac{T_U}{T_U+S}\Bigg)^{F_{obs}+1}$$
Where $\theta$ is the time of the first down time (in seconds) observed by the user, $T_U$ is the number of "up time" seconds observed , $T_D$ is the number of "down time" seconds observed, and $F_{obs}$ is the number of "down periods" (F for "failures"; $\frac{T_D}{F_{obs}}$ is the average number of seconds spent in "down time") observed
For your case, $F_{obs}$ is not given, but I would guess that you could find out what it was (which is why I gave the answer for known $F_{obs}$). Now because you know $T_D$, this tells you a bit about $F_{obs}$, and you should be able to pose an "Expected Value" or educated guess of $F_{obs}$, call it $\hat{F}$. Now using the geometric distribution with probability parameter $p=\frac{1}{\hat{F}}$ (this is the Maximum Entropy distribution for fixed mean equal to $\hat{F}$), to integrate out $F_{obs}$ gives the probability of (see details for the maths):
$$Pr(\theta \in (0,S)|\hat{F},T_U,T_D)=1-\frac{\Bigg(\frac{T_U}{T_U+T_D}\Bigg)\Bigg(\frac{T_U}{T_U+S}\Bigg)^2}{\hat{F}-(\hat{F}-1)\Bigg(\frac{T_U}{T_U+S}\Bigg)}$$
So for your specific case, the table below shows various bounds for different $F$, assuming it is known (column 2) or "expected" (column 3). Can see that the knowing $F_{obs}$ comparing to knowing a "rough" guess $\hat{F}$ only matters when it is very large, (i.e. when the observed average down time is 1 second or less).
$$
\begin{array}{c|c}
F & Pr(\theta \geq \text{S}|F_{obs},T_U,T_D) & Pr(\theta \in (0,S)|\hat{F},T_U,T_D) \\
\hline
1,000,000 & 0.625 & 0.499 \\
\hline
500,000 & 0.393 & 0.336 \\
\hline
250,000 & 0.227 & 0.207 \\
\hline
125,000 & 0.128 & 0.122 \\
\hline
62,500 & 0.074 & 0.072 \\
\hline
31,250 & 0.045 & 0.045 \\
\hline
15,685 & 0.031 & 0.030 \\
\hline
7,812 & 0.023 & 0.023 \\
\hline
1 & 0.016 & 0.016
\end{array}
$$
DETAILS
It is based on example 3 in the paper below
Jaynes, E. T., 1976. `Confidence Intervals vs Bayesian Intervals,' in Foundations of Probability Theory, Statistical Inference, and Statistical Theories of Science, W. L. Harper and C. A. Hooker (eds.), D. Reidel, Dordrecht, p. 175; pdf
It supposes that the probability that a machine will operate without failure for a time $t$, is given by
$$Pr(\theta \geq t)=e^{-\lambda t};\ \ 0<t,\lambda < \infty$$
Where $\lambda$ is an unknown "rate of failure", to be estimated from some data.
I will use this to model the failure times in 2 separate cases. Where "failure" indicates going from "working" to "down time", and the other way around. You can think of this like modeling two "memoryless" proceedures. We first "wait" for the down time, from time $t=t_{0u}=0$, to time $t=t_{1d}$ (so that there was $t_1$ seconds of uninterupted "operating" time). This has a failure rate of $\lambda_d$ At time $t=t_{1d}$ a new process takes over and now we "wait" for the down time to "fail" at time $t=t{1u}$. It is also supposed that the rate of failure is constant over time, and that the process has independent increments (i.e. if you know where the process is at time $t=s$, then all other information about the process prior to time $t<s$ is irrelevant). This is what is known as a first order Markov process, also known as a "memoryless" process (for obvious reasons).
Okay, the problem goes as follows, Jaynes eq (8) gives the density that $r$ units out of $n$ will fail at the times $t_1 ,t_2 ,\dots,t_r$, and the remaining (n-r) do not fail at time t as
$$p(t_1 ,t_2 ,\dots,t_r | \lambda,n)=[\lambda^r exp(-\lambda \sum_{i}t_i)][exp(-(n-r)\lambda t)]$$
Then assigning a uniform prior (the particular prior you use won't matter in your case because you have so much data, the likelihood will dominate any reasonably "flat" prior) to $\lambda$, this give the a posterior predictive distribution of (see Jaynes paper for details, eq (9)-(13)):
$$Pr(\theta\geq\theta_0|n,t_1 ,\dots,t_r)=\int_0^{\infty}Pr(\theta\geq\theta_0|\lambda)p( \lambda | t_1 ,t_2 ,\dots,t_r,n)d\lambda=\Bigg(\frac{T}{T+\theta_0}\Bigg)^{r+1}$$
Where $T=\sum_{i}t_i + (n-r)t$ is the total time the devices operated without failure. This indicates that you only needed to know the total "failure free time", which you have both given as $T_D=500,000$ and $T_U=31,556,926-500,000=31,056,926$. Also for you problem we always observed either $n$ or $n-1$ "failures" by time $t$, depending on whether the system was "down" or "up" at time $t$.
Now if you knew what $F_{obs}$ was, then you just plug in $r=F_{obs}$ to the above equation. The probability that a user will not be in the "down time" in the first $S$ seconds given that the system was "up" when they started is then
$$Pr(\theta\geq S|[\text{Up at start} ],F_{obs},T_U)=\Bigg(\frac{T_U}{T_U+30}\Bigg)^{F_{obs}+1}$$
But the story is not yet finished, because we can marginalise (remove conditions) further. To make the equations shorter, let $A$ stand for the system was up when the user started, and let $B$ stand for no down time in $S$ seconds. Then, by the law of total probability, we have
$$Pr(B|F_{obs},T_U,T_D)=Pr(B|F_{obs},T_U,T_D,A)Pr(A|F_{obs},T_U,T_D)$$
$$+Pr(B|F_{obs},T_U,T_D,\overline{A})Pr(\overline{A}|T_U,T_D)$$
Now $\overline{A}$ means that the system was down when the user started, so that it is impossible for $B$ to be true (i.e. no down time) when $\overline{A}$ is true. Thus, $Pr(B|F_{obs},T_U,T_D,\overline{A})=0$, and we just have to multiply by $Pr(A|F_{obs},T_U,T_D)$. This is given by $\frac{T_U}{T_U+T_D}$, because none of information contained in $F_{obs},T_U,T_D$ give any reason to favor any particular time over any other time.
$$Pr(\theta\geq S|F_{obs},T_U,T_D)=\frac{T_U}{T_U+T_D}\Bigg(\frac{T_U}{T_U+S}\Bigg)^{F_{obs}+1}$$
Taking 1 minus this gives the desired result.
NOTE: We may have additional knowledge which would favor certain times, such as knowing what time of day is more likely to have a system outage, or we may believe that system outage is related to the number of users; this analysis ignores such information, and so could be improved upon by taking it into account.
NOTE: if you only knew the a rough guess of $F_{obs}$, say $\hat{F}$, you could (in theory) use the geometric distribution (has largest entropy for fixed mean) for $F_{obs}$ with probability parameter $p=\frac{1}{\hat{F}}$ and marginalise over $F_{obs}$ to give:
$$Pr(\theta \geq S|T_U,T_D)=\frac{T_U}{T_U+T_D}\sum_{i=1}^{i=\infty} p(1-p)^{i-1}\Bigg(\frac{T_U}{T_U+S}\Bigg)^{i+1}$$
$$=\frac{T_U}{T_U+T_D}\Bigg(\frac{T_U}{T_U+S}\Bigg)\sum_{i=1}^{i=\infty} p(1-p)^{i-1}\Bigg(\frac{T_U}{T_U+S}\Bigg)^{i}$$
$$=\frac{T_U}{T_U+T_D}\Bigg(\frac{T_U}{T_U+S}\Bigg)\sum_{i=1}^{i=\infty} p(1-p)^{i-1} exp\Bigg(i log\Bigg[\frac{T_U}{T_U+S}\Bigg]\Bigg)$$
Now the summation is just the moment generating function, $m_{X}(t)=E[exp(tX)]$, evaluated at $t=log\Bigg[\frac{T_U}{T_U+S}\Bigg]$. The mgf for the geometric distribution is given by:
$$m_{X}(t)=E[exp(tX)]=\frac{pe^t}{1-(1-p)e^t}$$
$$\rightarrow m_{X}(log\Bigg[\frac{T_U}{T_U+S}\Bigg])=\frac{p\Bigg[\frac{T_U}{T_U+S}\Bigg]}{1-(1-p)\Bigg[\frac{T_U}{T_U+S}\Bigg]}$$
And this gives a marginal probability of (noting $p=\frac{1}{\hat{F}}$):
$$Pr(\theta \geq S|T_U,T_D)=\frac{T_U}{T_U+T_D}\Bigg(\frac{T_U}{T_U+S}\Bigg)\frac{\frac{1}{\hat{F}}\Bigg[\frac{T_U}{T_U+S}\Bigg]}{1-(1-\frac{1}{\hat{F}})\Bigg[\frac{T_U}{T_U+S}\Bigg]}$$
Rearranging terms gives the final result:
$$Pr(\theta \in (0,S)|T_U,T_D)=1-Pr(\theta \geq S|T_U,T_D)=1-\frac{\Bigg(\frac{T_U}{T_U+T_D}\Bigg)\Bigg(\frac{T_U}{T_U+S}\Bigg)^2}{\hat{F}-(\hat{F}-1)\Bigg(\frac{T_U}{T_U+S}\Bigg)}$$
