On both my run throughs I had found a longtooth just before I found the pirate so just keep on walking that area they are there somewhere. As far as the map goes I have never even looked at it yet, I just got the map because i had just picked up a long tooth skin so it was easy but its not going to be a game stopper not having the map.
------------------
......shake it baby.