I had this problem for a while, but eventually I accidentally stumbled across the answer. When you click on a cup or gym you are presented with three options. From left to right they read: Registered Pokemon, Register Pokemon, and Rental Only (Enter). Pick the one in the middle (Register Pokemon) and one of the options will be to "Delete registered Pokemon".
"I hate so much about the things that you choose to be." Cookies are awarded to users who get the reference. Cookies awarded so far -- 0