I would prefer your second solution, to strip the \n's first. Just like you, I would like to have a fancy regexp to do it, but if you install regexp's everywhere regardless whether it is the best solution for that particular case, it will turn out to be awkward, instead of smart. If you cannot come up a lean and clean regexp, I would rather not use it, remember regexp can be really difficult to understand. Especially in a corporate environment, you may well confuse whoever unfortunately has to maintain your code.

In your case, the problem is not just the \n's can come up at any random places within the replaced strings, there is another problem which is equally annoying, if not even worse: where to put the \n's in your replacing strings, so that it satisfies the 80-char restriction? Even worse, you may well have to shift all those \n's in all continue lines, within that logic record (,as it is possible that your logic record can spread into more than two lines). All what I am saying is that, there is a large chance, that you have to reformat your lines, lots of them, if not all.

Have said all this, I really see a clean solution would be:

1. strip those \n's caused by 80-char restriction. (You may have two types of \n's, one is the logical record separator, one is caused by the 80-char restriction. This is not clearly described in your post, I just go with a more complete thinking.)
2. do a s///, you don't need any fancy one, just a plain normal one, which anyone can come up in one second.
3. Reformat to satisfy the 80-char restriction.