Well, what do you know. I have found the solution.
Under "Delivery -> Advanced" I put my ISP SMTP Server as the Smart Host.
Then under Outbound Security I used Basic Authentication and put in my ISP SMTP username and password which my ISP provided me with.
And all works fine now, all of my Queued messages have been sent successfully.