We found Exchange 2010 needs a percentage of space left. We had this issue and had 2.5GB free on hard drive but could send internal email and send without issue.