Have you burned bootloader with a configuration that has the fuses configured to not jump to bootloader?
You need to "burn bootloader" with a board definition that doesn't have BOOTRST set (even though you are not using a bootloader, you still need "burn bootloader" to set the fuses), otherwise it will try to jump to the location where it's expecting the bootloader - and which, if you've uploaded a large program to it, is populated with program code now. The behavior of this could conceivably vary based on the contents of ram, and since some of the data in memory can persist with power off longer than you'd expect, it's not inconceivable that the behavior you describe could be generated.