Just as an idea, how about using a CR2032 lithium button battery as the backup? That delivers 3V for roughly 200 mAH.
I tested a sketch using the watchdog timer on this page: http://www.gammon.com.au/power
If you supply 3V rather than 5V the power consumption in sleep mode is 4.2 uA. My calculations show the battery (at that rate) would last around 5 years.
Maybe you could have a second processor with the lithium battery on it. Its job is just to wake up every 8 seconds and monitor the solar power output. If too low, it asserts reset on the second processor, and goes back to sleep. If high enough, it releases reset on the main processor (the one powered by the solar panel) which then gets to work without brownout issues.
But still I am concerned that the solar panel will just get up enough voltage to exceed the 85 brownout; the 85 will power up and exceed the current available from the panel; the voltage will drop; brownout occur; 85 drops out; voltage rises... and so on. How do I get around this?
Does this matter anyway? It will just keep resetting until the sun is bright enough.