If the last payment to our consultant dated 12/31/09 was sent out in the middle of January 2010, should we include this check amount in the 1099 for 2009?

Based upon the eight years I spent in a tax office, the answer to your question would be "no." Your contractor may have done the work in 2009 but your check was clearly sent out in 2010. There might have been a chance had the envelope (to him) been dated in 2009 but, if he needed to prove that there was a discrepancy in the amount, the fault would probably be yours.