As to terminology, page frame and page is normally two terms which refer to the same thing (a physical page/frame).
Demand paging doesn't mean that the page tables are not present in memory. Demand paging means that the actual pages/frames are not present in memory.
More often than anything, the page tables of a process should be filled according to how much memory is available. For example, on a system with 4GB of memory, the page tables should span 4GB. This is for security reasons. If the page tables are not filled completely, then a certain process A could access the memory of another process. This is due to the fact that, when the page tables are not filled completely, an address can be translated to anything (because anything could happen to be in memory at the time of translation). It is one of the mechanism of paging which allows great hardware isolation of one process to other processes.
Each entry of every page tables have a present bit. When the MMU of the processor attempts to access a page which isn't present, it triggers a page fault. The kernel thus takes the page on the hard-disk and loads it to main memory (unless the page wasn't supposed to be accessed in which case it kills the process).
Every executable today supports virtual memory. The virtual memory in use by a process is specified in the executable directly. The kernel thus uses that to determine if a process should have access to a specific address. It determines the ranges of virtual addresses that a process has access to in the executable.
In demand paging, the kernel just leaves the executable on the hard-disk and builds a memory map of the process. Then, when the process is given a CPU to run (by the scheduler triggered by a timer interrupt), the kernel jumps to its entry point. When the process starts executing, it triggers a page fault immediately. The kernel thus looks in its memory map for that process and determines that the access was legal according to the ranges of virtual addresses that the process has access to. It will thus put the accessed page in main memory reading it from the executable and then put the process back on the run queue.
Your assumption that the page tables are not filled is wrong. The page tables are filled. The entries are just marked as not present. I don't know about Linux or Windows. What I would do, if I wrote something like that, is I would fill all page tables of a process with zeroes. On page fault, I would then check whether the address access was zero and kill the process if it is the case.