Whenever an output doesn't behave the expected way and there are other operations on the same port (RLY and STX both on PortA in this case) I always suspect a read-modify-write issue - especially so when the operating frequency goes up. To verify if this is the case try inserting a short PAUSE between setting/resetting RLY and doing the SEROUT2.

Are you driving the relay directly from the PIC (heavy load) or do you have driver in between?

/Henrik.