Why is it sometimes possible to fold an infinite list from the right?

Your interleave is insufficiently lazy. The magic thing that right folds must do to work on infinite structures is to not inspect the result of the folded value too closely before they do the first bit of computation. So:

interleave x stream = Cons x $ case stream of
    Cons y ys -> Cons y (interleave x ys)

This produces Cons x _ before inspecting stream; in contrast, your version requires stream to be evaluated a bit before it can pass to the right hand side of the equation, which essentially forces the entire fold to happen before any constructor gets produced.

You can also see this in your list version of interleave:

interleave x list = [x] ++ intersperse x list ++ [x]

The first element of the returned list (x) is known before intersperse starts pattern matching on list.

We can inspect the source code of foldr [src]. A less noisy version looks like:

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Haskell does not evaluate eagerly. This thus means that, unless you need (foldr f z xs), it will not evaluate the accumulator. This thus means that f does not need the second parameter, for example because the first item x has a certain value, it will not evaluate the accumulator.

For example if we implement takeWhileNeq:

takeWhileNeq a = foldr f []
    where f x xs -> if x == a then [] else (x:xs)

if we thus run this on a list takeWhileNeq 2 [1,4,2,5], then it will not evaluate anything. If we however want to print the result it will evaluate this as:

   f 1 (foldr f [4,2,5])

and f will inspect if 1 == 2, since that is not the case, it will return (x:xs), so:

-> 1 : foldr f [4,2,5]

so now it will evaluate 4 == 2, and because this is false, it will evaluate this to:

-> 1 : (4 : foldr f [2,5])

now we evaluate 2 == 2, and since this is True, the function returns the empty list, and ingores the accumulator, so it will never look at foldr f [5]:

-> 1 : (4 : [])

For an infinite list, it will thus also result an empty list and ignore folding the rest of the list.