neverは「これまでに1度もない」ことを言います。

(1)はstrangerという見知らぬ人という前に会ったことが
　　「これまでに1度もない」人のことを言っているので
　　 neverです。
(2)はfirstとあり、訪れたことが初めてで前に訪れたことが　　　「これまでに1度もない」場所のことを言っているので
　　neverです。

have notだとまだしていないの意味になってしまいます。
私は経験していないことはnever
　　継続していない、まだしていないことはhave not
と使い分けています！