Android - How to revoke "SMS Services that cost you money" permission?

You can choose another setting by going into Settings > Applications > Applications Manager > More (top right) > Show System Apps > Message Service (rather than Messages) > Tap 'Send Premium SMS' > Select Ask, Never Allow or Always Allow.

On more recent versions of Android (Nougat V7) the setting is at Settings > Apps > Application Manager > More (top right) > Special Access > Use Premium SMS services (may be listed as Use Premium text message services) > Select Ask, Never Allow or Always Allow.

Well, bad news: It appears to be another of these annoying, huge Android bugs for which there's no solution yet.

The only workaround is to use another app for sending SMS, or to hard reset the phone.

From the discussion linked in the comments:

(...) the particular drop-down setting - for premium sms - you could toggle through back in an app's permissions in previous Android versions starting from 4.2. The case would arise if when using an app that required to send an sms to a 5-digit number, the OS would present a 'You might get charged' warning popup, which would prompt you to Allow or Deny sending the sms. If you also checked the "Don't ask me again" option then this warning popup would not appear again next time.

A user could reset that checked option in Settings> Apps (or Application Manager), going to the permissions section of the specified app and uncheck the premium sms "lock"; With Marshmallow though, there does not seem to be a similar option back in app settings.

The permissions toggles only enable/disable the standard SMS sending and have no effect on a premium sms locked option when they are enabled, leading to a blocking scenario where if a user had selected the "Don't ask again" option initially, he/she will not be able to resend an sms from the particular app.

Even worse is the fact that uninstalling and re-installing the app does not reset that initial selection, rendering the sending of sms to 5-digit numbers impossible and beyond the user's control.

In the discussion you can read the comments of other users which have the opposite problem -- they replied "No" and ticked "Don't ask again", and now they are forbidden from sending Premium SMSs.