Phantasy Star is definitely a judgement call. I'd say it falls under the "sort of rare, but highly desirable" category. In my SMS collection, I think that Aerial Assault, Ghouls N Ghosts, Psycho Fox, and Sonic are probably rarer than my Phantasy Star.

My Mega Man 7 and X3 for the SNES probably fall into that category too, although I know there's been some debate. My Tengen Tetris certainly does, though.

For certain rarities, I'd want to say Robot Killer for the Arcadia, which I thought might be one of it's more difficult finds (I need my guide!) Boxed NES Secret Scout is definitely a tough one. Qbert's Qubes for the 2600 (yay, finally!) is probably my rarest overall though...