Lately my “sent” messages are not being received. However, they show up in my Outlook “sent” box as having been sent. I even sent myself a message, and did not receive it.
Our email goes through Bluehost. Could the problem be with them?
In a nutshell, yes.
I assume you have tried sending message to a variety of people (not just to yourself) and they have not received the messages. If the fault was on your computer (whether with Outlook or some other part of the system), you would a) get an error message upon sending the message and b) the messages should have got stuck in the Outbox and not been copied to "Sent items".
All this points to the difficulty being with the sending server (SMTP or otherwise) which is part of your email-provider's infrastructure, so contact them and ask them to investigate.
If you are not receiving any emails (not just the one you sent to yourself), check your POP3/IMAP settings.
Messages are put into the "sent" folder after Outlook receives the final OK message from the outgoing email server. This merely means that the message was successfully sent to the server, not the recipient. If messages are not making it any further than that, you need to check with your email provider since it is highly likely that the problem lies with their server especially if you are not getting bounce/rejected messages from the recipient's email server.
I fully agree with Bruce. Since you can't even send emails to yourself it definitely looks like the problem is on your email providers end.