So I was playing Innsmouth and we had a couple Deep Ones move into the Unvisited Isle. Problem was Arkham was at its monster limit and the Deep Ones put it over. I'm assuming they go straight to the Outskirts but I'd like to make sure.

yeah, you played it right.