Error when using general and specific GRANT
You already found the answer to this problem. It all has to do with the order the grants appear.
Let's go back to your first grants display
+----------------------------------------------------------------------------------------------------------------+
| Grants for user@%                                                                                         |
+----------------------------------------------------------------------------------------------------------------+
| GRANT USAGE ON *.* TO 'user'@'%' IDENTIFIED BY PASSWORD '*XXXXXXXXXXXXXXXXXXXXXX'                              |
| GRANT SELECT ON `schema_%`.* TO 'user'@'%';                                                                    |
| GRANT SELECT, INSERT, UPDATE, DELETE ON `schema_user`.* TO 'user'@'%'                                          |
+----------------------------------------------------------------------------------------------------------------+

Here is how the grants are stored:

Information from GRANT USAGE is stored in mysql.user
Information from the other two lines are stored in mysql.db

To see this order, please run this query:
SELECT * FROM mysql.db WHERE db='schema_user' AND user='user'\G

This will display those grants in whatever order it was entered.
When you deleted the grants and reinserted them using
REVOKE SELECT ON `schema_%`.* FROM user;
GRANT SELECT ON `schema_%`.* TO user;

This reverses the order in the mysql.db table. To prove that, just rerun
SELECT * FROM mysql.db WHERE db='schema_user' AND user='user'\G

after doing the REVOKE and GRANT.
UPDATE 2017-08-02 13:20 EDT
In your comment, you said

I didn't knew of the mysql.db existence... But yes, it looks like it's the order; I suspected that already; but is this the expected behaviour? I would expect MySQL to &quot;merge&quot; the permissions so I didn't have to worry about order, since the grants are made by a SP automatically in here.

The problem here is MySQL will not merge them. For the sake of continuity, you should avoid using wildcards at the database level if your want to manage the grants of a single user. In that instance, you will have to manage the grants of  every single user the same way.