Mike, the best solution I can think of is to restore the deck surface w/ epoxy "barrier coat" primer (this stuff is very thick, sandable, & waterproof), and paintover that with polyurethane (nonskid can be mixed into this).