Welcome to Android Central! Which carrier? Do you always have strong cell signal? If your signal is poor and you don't have good mobile data connection, then MMS messages might have trouble sending.
Have you already spoken to Verizon about this? They might have some insight if there's a problem with your network locally. Or they might want to try reprovisioning the phone.