Deletion will always be possible. Even if you don't have a nuke at hand, there's always a sysadmin (or two, playing together) who can do it. If the value of "losing" audit logs is high enough, the solution will be found...
Most of the line printers have escape sequences to set many things. It's nice to use that to set the line feed distance to 0 points :-) [Can you buy a LP today that is dumb enough not to have such features? :-)]
Also, in most of the cases, you *can* change the logs (video tapes, etc.). Sure, it will be detected. So what? Applying crypto (hashes, HSM signed log entries, etc.) can show you that something was changed, but you'll never know what was the original data. For example: "What IP address did that hacker use, where did he come from? "Well, we don't know, but we do know that it's not what's in the log, as that is corrupt." Cool.
And yes, I'm being theoretical here. On the positive side, although you cannot say "once a log is written it can never be deleted or changed", you can mitigate the risk that this happens to you, down to a point where you (or SOX) find that acceptable.