I've gone through a second time from scratch, this time using a computer to deal with the more complex possibilities. I got stuck in the same place (earlier really, since I knew about the extra prime which the weird list withheld so I had one more unresolved entry). Eventually I decided that the idea was to try both possible solutions and see which one gave me the message, as a careful reading of the preamble suggests that sort of bifurcation was actually intended. (So the thing I'd thought before us likely irrelevant and my earlier question doesn't make sense.) I've ended up with the same grid as before so have submitted.
I do think this was a clever and interesting puzzle. I think it shows I'm uncomfortable with ambiguity, and not having a straightforward logical path all the time. (That said, I look forward to discovering there was something I missed when the solution is published!)
Thanks oyler for an enjoyable head-scratcher. (BTW the website you mentioned doesn't seem to have the list of primes, at least nowhere I could find by clicking around.)