I tried the new SIM card of a different carrier. I disabled the SIM card's PIN number and made sure there's enough credit to make calls etc (tried it first with my phone), so the SIM card generally works.
Let's verify there's no PIN.
AT+CPIN?
+CPIN: READY
OK
Ok, let's check the network. The AT+COPS? command now returns something much better. (before it'd reply with 0)
AT+COPS?
+COPS: 1
OK
From the documentation "1" stands for "Operator available".
Ok, that's good, let's check the signal now, which before was 0,0.
AT+CSQ
+CSQ: 21,0
OK
Very nice!
Let's turn the verbose errors, set the text mode on and try to send an sms.
AT+CMEE=2
OK
AT+CMGF=1
OK
AT+CMGS="00467692*****"
> test
>
+CMS ERROR: unknown
Aaaaaand nothing....

Let's try to make a phone call. Maybe that works.
ATD76922****;
OK
NO CARRIER
Nope. :/
So the behavior is definitely different than before, seems better, but still. Before i would get a "NO DIALTONE" reply when i'd try to make a phone call and generally i couldn't even get so far into the sending message sequence.
Any help would be greatly appreciated. Is there any chance that I have a "wrong" SIM card? This is just a normal SIM card that can make/receive calls and messages in all the standard networks (2G, 3G, 4G).