Hi Paul. I have been working around these challenges for about 10 years now.
how they are tightly bound to the kernel version
Actually, this has nothing to do with the kernel (Linus doesn't break userspace compatibility!) but with low-level libraries like glibc.
So the short answer is:
Yes, a "new" AppImage will run on "old" systems if you build on the oldest system you are targeting. The AppImage will run on this system and all newer systems. E.g., if you produce an AppImage on CentOS 6 then it will run on Ubuntu 16.04 just fine. In fact, that is what projects like Krita and KDevelop do to produce their AppImages. The Qt company also builds their Qt binaries this way.
The long answer:
It is possible to make AppImages that are compiled on a later build system and still have the AppImage run on (very) old target systems. However, this is a) complicated and b) bloated, since all dependencies down to very basic system libraries like glibc would have to be bundled. Hence, it is not the recommended route. But if you don't care about ca. 10 MB overhead, it certainly can be done.