The questions are:
(1)-Should NPB's be allowed to leave negative feedbacks?
Yes, certainly. I've been both a bidder and a seller on eBay for several years and have seen what can happen at both ends. I've seen capricious negative feedback left by sellers who didn't respond to repeated e-mails from the buyers, and I've seen the same kind of feedback from buyers who were dissatisfied that the item didn't reach them in three days or less. Let those who read the feedback make the judgement.
(2)-Does anyone have any suggestions on what can be done?
EBay will eventually take measures against chronic NPB's as you call them, but you can make it easier by filling out the proper complaint form irrespective of how lengthy it is. If you don't, and the NPB goes on his merry way with no sanctions from eBay, you have only yourself to blame. I also remind you that buyers have the right to refuse winning bids by persons with significant negative feedback. Put a statement to that effect in with your item description to give yourself that protection, and make a habit of checking the feedback of every winner.
Incidentally, I've only had one non-paying buyer out of all the hundreds of items I've sold.