Oracle index with REGEXP_REPLACE is it a good idea?
I don't have direct experience of an index with this kind of REGEX so I would avoid it by creating a 'standardised' telephone number column.

Create a process to go through the telephone numbers and store the clean, formatted version in the new column.

Perform the 'standardising' process on the user input and use that as a search against the new telephone column - which you will have indexed. 

The other option is to go through a data clean up process to standardise all the telephone numbers and ensure that any on-going input method applies the same process/validation.

EDIT:

The virtual column option mentioned above may be of use to you as well.

ALTER TABLE contacts ADD(search_telephone AS (REGEXP_REPLACE(tel_no, 'pattern', 'replace')).