You need to find an alternative source of information than where that excerpt came from as it is almost completely incorrect.
Strictly speaking a built in function is compiled into the matlab.exe executable, and hence neither you, nor I, can write a built-in function -- only The MathWorks can. However, many people mistakenly call m-files supplied by The MathWorks as built-in, and that is most likely what your excerpt is referring to.
For instance >> which plot will tell you it is built-in, and >> edit plot will show a file containing nothing but comments (which are the text help for the function).
Where as >> edit mean will open an executable m-file function in the edit. This is supplied by The MathWorks but is not built-in.
Referring to your specific question, there has _never_ been a requirement for the m-file to exist for using a mex-file, and mex-files have _never_ been recompiled each time they are called. That's presumably why you can't find anything about those topics in the documentation.
All you need to write a mex file is a properly written (using the mex API) .c file and a C compiler. (You may need other headers, source files, libraries etc if you are calling some external libraries from your mex file, but that has nothing to do with mex or MATLAB, but rather with just getting the code to compile correctly.)
Before being able to call your mex file from MATLAB you need to "mex" it using the mex function, which is does the compilation to a shared library (with a different extension depending on your OS) for MATLAB to use. Once you have done that (only once) you can call the mex file in exactly the same way as you would call an m-file equivalent. An m-file equivalent does _not_ have to exist, and if it does it will not get called (as per the doc you cite).