Как выяснилось, приведенный ниже способ для Oracle не работает. Но для тех, кто будет искать похожий ответ при работе с неоракловыми регулярками - может оказаться полезным.
Попробуйте вместо .* применить [\s\S]*
Дело в том, что метасимвол . (точка) означает один любой (почти) символ, но в некоторых реализациях исключая символ перевода строки.
А символьный класс \s всегда включает символ перевода строки. Тогда выражение [\s\S]* будет соответствовать любому количеству любых символов, включая перевод строки.
regexp_substr(col, '<message>(.*?)</message>', 1, 1, 'n', 1) from DUAL
поможет?