Poly's pretty finiky, as you seem to have figured out with this build... and you probably already knew.
Now... what to do...
There's a tutorial on the main site that shows you how to scallop your frets. In this tutorial, it shows you how to wrap your frets (even a little under the fret) with masking tape. You can use this to mask your frets. Then you can use chemicals to strip the fretboard, as abraisives would just cause more problems than solutions. Then you can respray and scrape the binding, and the tape should help protect the frets against the chemicals, sprayover, and scraper. Then you can carefully peel the tape off your frets...
There shouldn't be any problem with using poly over shellac provided one has time to cure before the other is applied. I would have to say that any finish that is put on the fretboard is probably going to wear off over time. I'm not trying to sound condescending when I ask this, but why don't you just use shellac? why cover it in poly after?