I had the same problem. So I was helping a friend up in the towers (where you light up the crystals) and defeated a loathsome creeper and got what I needed.
I was also having the same problem with the pirates. I just keep battling them and not getting the note. So I went up in the tower by the crystals and found one with a pirate. Defeated him and got what I needed.