>I am starting to think that it is the baud rate generator component not
resetting correctly after being 'scrambled' at low voltage.  If there is no
way in software to fix this then circuitry to guarantee that VDD goes to 0 V
will need to be added.
>
Yeah, I had the same sort of problem when a '55 design of mine was "halfway
powering" itself from an external I/O line!  I found that the current draw
of the pic is so low that the meter's impedence would cause it to reset
properly!  I would say overkill is always the best policy....  Get that
voltage down!

A temporary solution for me was a relay that ran off the +5V and powered the
PIC.  The relay shut off as soon as the power droped under three volts and
switched the PIC's +5V line into GND.  Later on I just optically isolated
the I/O's.