Sent SMS via Twilio failed
Found the solution at the page mentioned: 
Turns out out it works with +15005550006 which means, there are still the test credtentials in the CiviCRM SMS Provider settings. Once they were replaced by the Live API information the earlier number also works. 

Makes perfect sense to me.