Yes I'm using internal internal oscillator @8MHz.
I'm not sure if the problem is the fact I'm not using caps because this would cause the chip to restart, right? And It's not.
My first thought was a bad quality atmega328 but I have never heard anything about it anyway :)
Could do all sorts of strange things. What happens is data corruption. You can't see it but at random times the supply can drop or increase to all sorts of values during a few ns or ms. This has to do with the power source impedance, PCB tracks, power consumption, natural switching of the internal pins on and off and most importantly ESD since there is no low impedance path for this short HV peaks to flow, other than the chip itself. Have a look on wikipedia on how flash memories work and what happens after they are work out. Leakages. Just the same as a ns pulse may do.
Electrolytic reserve capacitors are an optional extra that should be placed as good practice.
Ceramic decoupling capacitors are a must required for correct operation and should ALWAYS be placed.
The other possible issue is the bootloader not being correctly write protected. There is a locked area of the memory set by fuses. If incorrectly programmed the bootloader itself can get deleted and the chip wont start. But this will typically happen during upload of new code. The code is there, but without the bootloader it will never execute it and you cant update new code either.