To try to clarify a little:
I think Ben did mis-speak a couple of times in his response above. As Bert said/Ben meant...
One of the choices below "Inbox" in the messages is "Outbox". Another is "Deleted items".
I believe items stay in your "Deleted items" folder until you restart AC; even simply logging out will clear that folder.
I believe items stay in your "Outbox" until the recipient has deleted them (just opening them still leaves them in your "Outbox").
So you are right, there is no reliable "Sent" folder that you can go back to in case the recipient has BOTH inadvertently deleted your message AND logged off.
If this is really a recurring problem for you, I would suggest sending messages to more than one place. There are several ways to implement this, depending on your office. For example:
what always works (but is tedious) is to create a "dummy" recipient/staff box, and always cc: messages to that box.
On the other hand, if you only have one provider in the office, set up a dummy provider, and have everyone get in the habit of sending messages to "all providers" (that's is just one click, unlike the cc: approach I just mentioned). Have your provider use his provider box as his inbox.
Sounds complicated, but it really isn't too bad...but yes, it is a work around and a more robust messager would be nice.