Update:
My provider is Hungarian Telekom, talked to their agent, they checked and didn't find any issues on their end. They suggested I check which number is set as the SMS service number (should be +36309888000), but didn't find a setting that set's this either in the default SMS app (where it could be) or the settings.
So I downloaded the Google Messages app which includes a setting called SMSC. This included some random number and a question mark in the form of nnnnnnnn?n
. I was told this is what we're looking for, and to replace it with the number above. However this setting does not stay and always resets after pressing OK and exiting. What could be the issue?