I'm still having the problem that it remembers my selection, but it still doesn't open links in new windows. I've reloaded the page numerous times, tried it on different computers, and so on. But even though the box is checked, it still doesn't open links in new windows.
The only way it works is to uncheck the box, and then check it again. But then it does the same thing next time I open Safari, even if I reload the page.