Something's automatically sending "stuff" from my phone
If that is a malware, it will take care to leave no tracks (i.e. deleting the sent message).

Two things you should do ASAP:


Contact your provider and check what messages where sent. Especially expensive "Premium" messages. It could be something sends "just spam", but it also could be some "money generator".
Check with a permission checker what apps have the permission to...


send SMS/MMS
deactivate your lockscreen (aka keyguard)



If you find an app that has both permissions, that's a very likely candidate. A good app to check this is e.g. RL Permissions, which lets you check by app and by permission:

 
RL Permissions: Apps by permissions / Permissions by app (source: Google Play; click images for large variants)

As RL Permissions has not been updated for more than 2 years, an alternative to this is Permission Explorer, which offers similar features:

 
Permission Explorer: Apps by permissions / Permissions by app (source: Google Play; click images for large variants)

Once you've identified a suspicious app, deactivate or uninstall it. Watch if the described behaviour continues. If it does not, you've got the culprit.

One more lesson learned: Just having some AntiVirus on your device doesn't mean you're safe and don't need to care. Those "checkers" mostly compare with a database of known malware. Unlike their PC companions, they don't do heuristic scans.