I have faced the same problem earlier and it seems to happen for both clustered and non clustored setup. For us restarting the Microsoft Exchange Mail Submission Service and setting it to automatic on the non-clustered Exchange 2007 setup Mailbox role server has done the job.
For the clustered Scenario we had to start the Microsoft Exchange Mail Submission Service on the active node and add it to the cluster componenets as a service.
That resolved the issue for us.
Please post back your result