Where do they come from?

When the elements in an antenna array are spaced too far apart compared to the wavelength, you can end up with grating lobes. The ideal spacing is half-lambda, but it can get tricky when dealing with wideband antennas.
 
Does the spacing between antenna elements always have to be less than half the wavelength?

For extreme steering angles it is necessary, but in reality, it's not always practical to steer the beam +/-90 degrees. There are factors like the characteristics of the antenna elements themselves and other issues that come into play when designing arrays. So, while keeping the spacing below half the wavelength is ideal, it's not always a rule or possibility.