You should use 'dotall' modifier. Often it is 's' in other languages and here 'n', it's easy to miss it in documentation.

By the way, why you're using NOT is it some trick for optimizer?

SELECT CASE WHEN REGEXP_LIKE(MYSTRING, '^[a-zA-Z0-9]*$', 'n') THEN 'valid'
       ELSE 'invalid'
       END 
FROM DUAL