When this method is called on a window with a value of false the always-on-top state is set to normal. The window remains in the top-most position but it`s z-order can be changed as for any other window.

The window remains in the top-most position...
It is not true for some window managers on Linux, e.g. Metacity:

If we have two windows #1 has always-on-top state and has no window focus and #2 has window focus,
then calling setAlwaysOnTop(false) will bring #2 window to front of #1 window.

The javadoc for the Window.setAlwaysOnTop should be updated to specify this platform specific behaviour.