2) Yes. You will see things taking twice as long, serial baud rates being half what you expected, etc.
Reduced speed does matter because the system won't seem as responsive, perhaps leading to extra button pushes, delayed output on LCD screens, etc.
Operation is guaranteed at 20 MHz, so at 16 its already running at a derated speed. Further derating does not gain anything.
I've had 14 Promini's & standalone equivalents running at 16 MHz at my fencing club since Dec 2010, 3-4 classes a week for hours at a time. We go in, turn on a power strip, and 3-5 hours later turn off the strip & go home. They've worked great.
Main score/time box with 2 16 MHz Promini's
Remote control for main box, 3.3V/8MHZ Promini running in 1000mAH LiPo
Smaller boxes that only show touches being scored, some have Promini's, some are built-up equivalents
All are wirewrapped.
I realize that's only anecdotal. Does he have anything to offer for comparison?
At the same time, this Sony Vaio I am typing on gets used for more hours at a time at an waaaay higher clock speed (2200 MHz) on a daily basis, and it seems pretty reliable too, 3+ years old and runs much warmer than any arduino.