I wanted to add that BOD is not as simple as "on" or "off" and has multiple levels that it can be set for. In order to determine whether you're going to get rogue instruction execution you need to make sure your clock speed matches your BOD setting. For example, you can set a BOD of 1.8V if you're running 2Mhz or less. You'll want a BOD of 2.7V for 8Mhz and 4.3V for 16Mhz+. Double-check those exact numbers with the datasheet.
If you choose a BOD setting too low for your given clock speed you'll indeed get incorrect/rogue execution of instructions at some point. Is it possible you are using the default BOD of 2.7V and 16Mhz? That would explain the instability. If you can slow the clock down you can run reliably at lower voltages. The best option considering the needs of your RTC seems to be BOD of 2.7V and 8Mhz. Try that.