Hi Kristof,
I recall having similar issues years ago (GMT4 or 5), although not with categorical data. If I remember correctly, this is related to antialiasing - the -n+a option in grdimage.
I was able to plot your grid in what seems to be the actual values (no fringes) albeit the maps look the same with and without the -n+a option. See attached. Didn’t have the xy location to replicate your map frame.
gmt grdimage -JM10c cv_discclass.grd -C<yourcpthere> -R-23.8/-23.4/14.8/15.3 -png caboverde -Bafg -n+a
Without -n+a:
With -n+a:
This is on MacOSX 10.15, GMT 6.2.0_ee02ffa-dirty_2020.10.25
Cheers,
Christian