This is the forum for the CorelDraw suite and PSP isn't supported here but:
When you draw a rectangle in Paint shop pro it is a vector object. You must set the outline thickness larger than the default for the outline to be apparent.
Next: You must save the image as a PSP Image file - not a JPG or Tiff to maintain the outline's editability.
I just tested and my outlines are sticking.