Then, there is the case that such an operator is defined on the full interval
I assume that by "full interval" you mean the whole real line.
First question: Do we then need any boundary conditions?
Yes, as noted by Sam Bader, boundary conditions are part of the Hamiltonian.
In my physics lecture we used so-called Born von Karmann boundary conditions ... in order to "prove" the Floquet or Bloch theorem
Indeed, Bloch's theorem requires translational symmetry. If you limit your domain to some finite interval, then such a symmetry is only achieved with periodic boundary conditions.
But, when your domain is the whole real line, there's no need to impose special boundary conditions to achieve translational symmetry: just the usual condition of boundedness of the solution is enough. See e.g. a special case — free particle Hamiltonian: It requires that the solution is bounded at infinity, and that's enough to get the solution as plane waves. And it does have translational symmetry, thus has conserved quasimomentum (which in this case coincides with momentum because period of this symmetry is arbitrarily small).
I somehow feel as if these Born von Karmann boundary conditions are not necessary in the sense that any eigenfunction to this Schrödinger operator is automatically periodic with the potential's period, is this true?
This is wrong, and explained properly by Steve B.
My problem with the Born von Karmann conditions is that I find that they are not really boundary conditions, as they don't act on some boundary. So what about the domain of such an operator?
They do act on the boundaries of the domain: if your finite domain is $[a,b]$, then you have
$$f(a)=f(b),\\
f'(a)=f'(b).$$
This is precisely what Born — von Karmann conditions are about. If you try to implement these conditions in a matrix representation of your kinetic energy operator, you'll get a circulant matrix, which explicitly shows the translational symmetry. (Try to play with finite differences approximation of kinetic energy operator, you'll see this directly).
In my physics lecture we noticed that due to these Born von Karmann conditions the possible k′s for the problem (appearing in the exponentials) are discrete. Not sure if this is automatically satisfied, even if we don't assume Born von Karmann boundary conditions?
Indeed, even if you don't take Born — von Karmann boundary conditions, and instead take e.g. homogeneous Dirichlet or Neumann boundary conditions, you'll end up with discrete spectrum. That's the result of finiteness of the domain and is a general feature of Sturm—Liouville problem.
Then we said that for every k, the Schrödinger operator equation that you get by pluggin in the ansatz from the Bloch or Floquet thoerem has a discrete spectrum. Is this true?
Again, it is true as long as you have a finite domain. And Bloch theorem makes direct sense only in presence of translational symmetry, i.e. with Born—von Karmann boundary conditions in this case.
If so, what does this all have to do with bands, if everything is so nicely discrete? - Or do we just cal these things bands, since the k's get so close, that we cannot really resolve the discrete structure?
The continuous bands appear when we take the limit of crystal size $L\to\infty$ (i.e. take number of lattice cells to infinity). In this limit Born—von Karmann conditions just automatically transform into the conditions of boundedness of the solution at infinity, and as you increase number of lattice cells, the spectrum becomes more and more dense (i.e. the discrete levels corresponding to some $k$ come closer and closer to each other while their number increases), and in the limit of $L\to\infty$ it becomes continuous.
Note that on infinite domain you can't apply Born—von Karmann conditions — it doesn't make sense to say $f(-\infty)=f(+\infty)$, for instance, so you use the natural conditions of boundedness.
This is an approximation to the real crystal, in which there's a huge number of atoms in all (or some, for e.g. graphene) directions, so that we can really just suppose that it's infinite in the first approximation.
In real crystals the spectral lines are so dense, that they indeed can't be resolved — but this is not only because of instruments: it's because of natural widening of spectral lines: the uncertainty of the level energy due to finite lifetime because of spontaneous emission.
Is there any relationship between the finite-interval problem and the infinite interval problem or are these two completely different things?
Yes, the relationship is as I noted above: via a limit. There appear some subtle differences though, like the fact that eigenfunctions in the infinite domain become unnormalizable, and the spectrum becomes continuous, but physically it's still quite similar. Again, you can play with empty lattice approximation (i.e. Hamiltonian with constant potential) to better understand the properties of these problems.