Derangements would be permutations with all cycles of length at least 2; this question asks about all permutations with cycles of length at least 3. At first glance the problem looks like it could be very interesting, but actually to get the desired result requires only a tiny amount of analysis. Let us count the contribution to $D_1(n + 1)$ (respectively, $D_0(n + 1)$) that comes from permutations in which the entry 1 appears in a cycle of length $k + 1$. There are $\binom{n}{k}$ ways to choose the other entries to go in this cycle and $k!$ ways to choose which cycle to make with the $k + 1$ selected entries. Then the remaining $n - k$ entries must also be divided into cycles. If the result is to have an odd (respectively, even) number of cycles, then the remaining entries must be divided into an even (respectively, odd) number of cycles. Thus, \[ D_1(n + 1) = \sum_{k = 2}^n \binom{n}{k} k! D_0(n - k) \] and \[ D_0(n + 1) = \sum_{k = 2}^n \binom{n}{k} k! D_1(n - k). \] Taking the difference of these two equations and rewriting $\binom{n}{k} k! = \frac{n!}{(n - k)!}$, we have \[ D_1(n + 1) - D_0(n + 1) = \sum_{k = 2}^n \frac{n!}{(n - k)!} (D_0(n - k) - D_1(n - k)). \] Since $k \geq 2$, the first factor in each summand is divisible by $n$, while the second factor is an integer. So we have a sum of numbers divisible by $n$, which is certainly divisible by $n$. (Actually, we get for free from this argument that the difference $D_1(n + 1) - D_0(n + 1)$ is divisible by $n(n - 1)$.)

Let $a_n = D_1(n) - D_0(n)$. Just to make sure I understand the problem correctly, I get $a_3 = 2$, $a_4 = 6$, $a_5 = 24$, and $a_6 = 80$. Are those values correct?

That agrees with my understanding. (For $D_1(n)$ I have 0, 0, 0, 2, 6, 24, 120, 720, 5040, 42560, 413280 and for $D_0(n)$ I have 1, 0, 0, 0, 0, 0, 40, 420, 3948, 38304, 396576 as $n$ goes from 0 to 10.) I guess I should also say that throughout my solution I was using the identification "a division of the beads 1 to $n$ into some number of cycles" with "a permutation of length $n$, given in cycle notation," though of course the counting argument works just as well if one wants to go put the words "beads" and "necklaces" where I've put "entries" and "cycles." Also FWIW, I think that the generating functions for the two series are \[ \sum_{n \geq 0} D_0(n) \frac{x^n}{n!} = \frac{1}{2}\left(\frac{\exp\left(-\frac{x(x + 2)}{2}\right)}{1 - x} + (1 - x)\exp\left(\frac{x(x + 2)}{2}\right)\right) \] and \[ \sum_{n \geq 0} D_1(n) \frac{x^n}{n!} = \frac{1}{2}\left(\frac{\exp\left(-\frac{x(x + 2)}{2}\right)}{1 - x} - (1 - x)\exp\left(\frac{x(x + 2)}{2}\right)\right), \] if I haven't made any errors. (One can derive this from the recursions by solving a differential equation.)

Then I conjecture that $a_n = (n - 1)(n - 2) b_{n - 3}$, where $b_n$ is the number of involutions on $n$ elements.

Good conjecture: we can extract it from the GFs I gave, since taking the difference gives \[ A(x) = \sum_{n \geq 0} a_n \frac{x^n}{n!} = (x - 1)\exp\left(x + \frac{x^2}{2}\right). \] Your conjecture is equivalent to $A'(x) = x^2 \sum_{n \geq 0} b_n \frac{x^n}{n!}$; this is easy to check using the known GF $\sum_{n \geq 0} b_n \frac{x^n}{n!} = \exp\left(x + \frac{x^2}{2}\right)$. But obviously this is not totally satisfactory (for one thing, I've just pulled the GFs for $D_1$, $D_0$ out of thin air); a combinatorial proof would be nice.