Added: Please see the end for a very simple way to solve the problem.
We assume that cards are removed from the deck until only face cards are left. (So a referee tells us when to stop.) We want the probability that at that time, the Ace of Hearts is still in the deck.
It is clear that if the referee lets us go through the whole deck, because the last card isn't a face card, the Ace of Hearts is gone.
There are $16$ individual cases to examine: (i) the last card is a face card, but the one before is not; (ii) the last $2$ cards are face cards, but the one before is gone; (iii) the last $3$ cards are face cards, but the one before is not. Continue in this way until case (xvi), the last $16$ cards are face cards.
Case (i): The probability that the last card is a facecard (F) is $\frac{16}{52}$. Given it is an F, the probability the previous card is NF is $\frac{36}{51}$. So the probability we end with NF, F is $\frac{16}{52}\cdot\frac{36}{51}$. Given that this has happened the probability the last card is the Ace of Hearts is $\frac{1}{16}$, for a probability of $\frac{16}{52}\cdot\frac{36}{51}\cdot\frac{1}{16}$.
Case (ii): The probablity the last card is F is $\frac{16}{52}$. Given that, the probability the previous card is an F is $\frac{15}{16}$. Given that, the probability the previous card is NF is $\frac{36}{50}$. Given all that, the probability that the Ace of Hearts is still in the deck is $\frac{2}{16}$. So our case (ii) probability is $\frac{16}{52}\cdot\frac{15}{51}\cdot\frac{36}{50}\cdot\frac{2}{16}$.
Case (iii): The probability that the last $3$ cards are $F$, but the fourth from the end is NF, is $\frac{16}{52}\cdot\frac{15}{51}\cdot\frac{14}{50}\cdot\frac{36}{49}$.
Given this has happened, the probability the Ace of Hearts is among the last $3$ is $\frac{3}{16}$. So the probability of case (iii) is $\frac{16}{52}\cdot\frac{15}{51}\cdot\frac{14}{50}\cdot\frac{36}{49}\cdot \frac{3}{16}$.
I hope the pattern is clear. One has to add up all of these. There is undoubtedly a much simpler way to view things. Certainly one can express the products above in terms of binomial coefficients. That part is not very interesting, but I think there is a way to avoid summing.
A much much simpler way: Don't worry about all the face cards except the Ace of Hearts. Confine attention to these $37$ cards.
The Ace of Hearts survives precisely if it is the last card among the $36$ non-face cards and the Ace of Hearts. Since any order of these $37$ cards is just as likely as any other order, the probability the Ace of Hearts is last among them is $\dfrac{1}{37}$.
There are two ways to get the correct solution. The easier way is to consider the set $\left\{\left[5k\right],\left[5k+1\right],\left[5k+2\right],\left[5k+3\right],\left[5k+4\right]\right\}$ of congruence classes modulo $5$ (where $\left[5k\right]$ simply denotes the class with representative of the form $5k$ for an integer $k$, and so on). The probability that you would pick any one of these classes is $\frac{1}{5}$. Thus, the probability that you would pick the class $\left[5k\right]$ is $\frac{1}{5}$. The probability that you will not pick this class is $1-\frac{1}{5}=\frac{4}{5}$. The probability that you would pick $4$ classes that are each not $\left[5k\right]$ is $\left(\frac{4}{5}\right)^{4}=\frac{256}{625}$. Therefore, the probability that you will have a product divisible by $5$ is equivalent to saying that at least one class is $\left[5k\right]$, which has probability $1-\frac{256}{625}=\frac{369}{625}$.
The second method, which is more popular when such classes are not possible, is to take probabilities over the integers in the interval $\left[1,n\right]$, and look at the behavior of these probabilities as $n\to\infty$. Though this is not needed here, it is a good technique to know.
Best Answer
$$\binom{n}{12}=\frac{n(n-1)(n-2)\ldots(n-11)}{12!}=\frac{n(n-1)(n-2)\ldots(n-11)}{2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11}$$
Any $12$ consecutive integers include $4$ consecutive factors of $3$, at least one of which must be a multiple of $9$, and six consecutive multiples of $2$. Three of these must be multiples of $4$, and at least one must be a multiple of $8$, so their product has at least $10$ factors of $2$. We want to know when the product has at least $6$ factors of $3$ and at least $12$ factors of $2$.
The $12$ integers include two multiples of $9$ if $n$ is congruent to $0,1$, or $2$ modulo $9$, and they include a multiple of $27$ if $n$ is congruent to $0,1,2,\ldots,10$, or $11$ modulo $27$; thus, their product has at least $6$ factors of $3$ if and only if $n$ is congruent to one of the following $15$ numbers modulo $27$:
$$0,1,2,3,4,5,6,7,8,9,10,11,18,19,20$$
If the $12$ integers include two multiples of $8$, one of those must be a multiple of $16$, and their product will then have at least $12$ factors of $2$. If they include only one multiple of $8$, it must be a multiple of $32$ if the product is to have at least $12$ factors of $2$. They include two multiples of $8$ if $n\equiv 0,1,2,3\pmod8$, and they include a multiple of $32$ if $n$ is congruent to $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, or $11$ modulo $32$. Thus, their product has at least $12$ factors of $2$ if and only if $n$ is congruent to one of the following $20$ numbers modulo $32$:
$$0,1,2,3,4,5,6,7,8,9,10,11,16,17,18,19,24,25,26,27$$
$\binom{n}{12}$ is a multiple of $12$ if and only if $n$ satisfies both of these conditions, meaning that it is in one of $15\cdot20=300$ residue classes modulo $27\cdot32=864$. As noted in the comments, the expression randomly chosen natural number is at best ill-defined, but we can at least say that the natural (or asymptotic) density of the set of natural numbers $n$ such that $12\mid\binom{n}{12}$ is
$$\frac{300}{864}=\frac{25}{72}\;,$$
and this corresponds reasonably well to the intuitive notion.