I should have put this in my top technical support issues blog as this is about as common of an issue as it gets. I can't tell you how many times I've heard Great Plains. I can't void out a payment because it's applied to an invoice that still has amount outstanding. I also can't void out the invoice as it has a payment applied to it.
This is one of the most rinky dink processes but this is the resolution for both receivables or payables:
The same would be true if the invoice is fully applied and there is still an outstanding amount on the payment. Create a dummy invoice and apply it to the payment. Then you can void the payment and the dummy invoice.
As Mariano says, "Don't shoot the messanger".