I just completed some experiments with this very problem using nagios 3.2.0 on RHEL5.2. Here are the characteristics that I have found.
Service A Critical hard state reached and corresponding notification sent
Downtime scheduled for Service A's host until well beyond when the recovery occurred.
Service A Recovery hard state (Ok) reached and corresponding notification sent.
The next test I did was to verify that I didn't need to schedule downtime for the service as well, so I repeated the above scenario except that I scheduled downtime for Service A and for Service A's host. The results were the same. Finally, as a sanity test, I did the following...
Schedule downtime for Service A's host (only host downtime) until well beyond the next set of tests.
Service A Critical hard state reached and NO notification sent
Service A Recovery hard state (Ok) reached and NO notification sent.
I still need to verify this on 3.2.3. I will do so and post results when I get to it. This begs the question though as to why a notification was sent out during a scheduled downtime window. The only difference here is that the service entered the non-OK hard state before the downtime began. If all events occurred within the downtime window, it worked exactly as expected.
In my opinion, this appears to be a bug in the code, but I'm willing to listen to reasoning as to why it would behave in this fashion. This appears to be a seldom encountered scenario, however, if you forgot to schedule down time for something until after you started maintenance, it's kind of a pain to get these notifications while you're in the outage window and there doesn't appear to be any way to stop them unless you specifically disable notifications for the service.