If you look at the OpenMP V2.5 spec, section 3.2.3 omp_get_max_threads states:
The omp_get_max_threads routine returns the value of the nthreads-var internal
control variable, which is used to determine the number of threads that would form the
new team, if an active parallel region without a num_threads clause were to be
encountered at that point in the program.
The following expresses a lower bound on the value of omp_get_max_threads: the
number of threads that would be used to form a team if an active parallel region
without a num_threads clause were to be encountered at that point in the program is
less than or equal to the value returned by omp_get_max_threads.
Your program is looking at the number of threads in the current region and the max threads number for the next region. So yes, it is possible to have omp_get_max_threads() < omp_get_num_threads(), because omp_get_num_threads() is returning the number of threads in the current parallel region and omp_get_max_threads() is returning the number of threads that would be in the next parallel region if a parallel construct were encountered where the call to omp_get_max_threads() was made.
The thing of interest to me, is that the implementation seems to also be considering the value of OMP_NESTED when returning the value of omp_get_max_threads. If you look in section 2.3 Internal Control Variables, it says that the nthreads-var value is what is returned when you call omp_get_max_threads() and that omp_set_num_threads() (or OMP_NUM_THREADS) is the only way to modify the value of nthreads-var. If this had been done by the implementation, then I would have expected the values returned by your two calls to be the same. However, if the implementation also takes into account whether nesting is allowed (or supported), then nthreads-var would be 1 as returned by your call.