When the machine is rebooted or shut down, processes will receive SIGTERM first, having a chance to terminate cleanly, after five seconds the remaining processes will be forcibly terminated with a SIGKILL. You can check for yourself reading the /etc/init.d/halt script in a Red Hat Linux installation.
As you say, SIGKILL cannot be caught so it won't trigger the END block. However, it is bad practice to abruptly terminate a process with SIGKILL without trying SIGTERM first.
Finally, as long as the signals you're handling can be caught and make your script die, the END block should always be executed. Why not having the cleanup code in the signal handler itself, though?
As a side note, why don't you try to detect and delete the stale database record at startup if possible? This seems safer and it prevents loopholes as well, for example if the process is terminated with SIGKILL.