Is it possible to have a MCU work at -55 degree, with specification of -40 to 85 degree working environment?
The crude way you'd ensure you were not on the edge of operation would be to test it outside the range. For example, you might test the parts at -65°C at voltage at a higher clock speed and higher/lower voltage than normal. 

The manufacturer probably does not test at temperature extremes themselves, but they know how much margin is required under test conditions and they test to that. They also know how to ensure that they are testing everything. You don't know any of that. For example, something like an oscillator might work fine down to -40°C, and once started work to very low temperatures, but some may fail to start at -45°C. One particular instruction may start to fail first because of some timing conditions. 

If the manufacturer can supply units qualified to that temperature that would be best. Or lobby for a relaxed requirement. Or put heaters in there to guarantee a minimum temperature after an acceptable warm-up period (perhaps inhibit operation until acceptable temperatures are reached). 

Chances are if the parts need to meet a military lower temperature range, you really need to be sure that it works reliably.