Generally, yes.
PO Boxes are some of the safest addresses available.
With a PO Box, if the item doesn't fit into the box itself, the owner of the box has to go to the counter and claim it from the clerk.
The Box renter has to present ID to the PO just the rent the box in the first place.
The reason you will see 'no PO boxes' from time to time has little to do with the PObox and a lot to do with couriers. Many US sellers use couriers, like UPS, because for domestic shipping they are fast, tracked, pick up at the sender's home and reasonable priced. However, they can't deliver to PO boxes, because the PO clerks can't and won't sign for packages. (Only the owner or his agent can do that.)
As for the Malaysia question. You are not shipping to Malaysia. Once the parcel reaches the US address, you are in the clear. Use tracking to the US address if you are concerned or if the item is too expensive to lose. If you can show that the parcel was delivered to the address you were given by Paypal (not eBay, Paypal) you will prevail in an Item Not Recieved dispute.
