What version of Sage are you on? You can tell by going to Help menu / About or File > Run > *INFO and pressing Enter. Shot in the dark guess is that since it was working before, and Test Email from Company Maintenance works, that since internal recipients fail too, that you go into Paperless / Setup / Form Maintenance and review the entry you have setup for Direct Deposit Stub.

Look at the From address and ask your IT if that particular address is no longer allowed to send / relay from the Exchange Server. Maybe it has been all this time but recently it changed (maybe). I've seen several times where Test works but Paperless forms (invoices, orders, a/p checks, direct dep stubs) do not because the From address was not allowed on Exchange. Usually all the outbound emails are sitting in some kind of Unsent folder. Hope that helps.