I know you're not protected by Paypal (such as the "protection" is) if you don't ship to a verified address. But what if Paypal's not involved at all? I just sold an item and the buyer will send a USPS Money Order for payment (as I required) but asked that I ship the item to the address with the money order rather than the one listed in the eBay email.
I'll know more in terms of matching names, etc. when I actually get the money order with the other address, but as long as the USPS money order is good, which I'll have cashed/confirmed at the post office, I don't see any issues here, do you?