Sorry to bump an old topic, (I Read the rules and saw that bumping is acceptable if you are contributing to the topic?)
As for Linebeck's story, he tells part of it during the mini part of Jolene's ambushes, I think once you get a letter off her in PH, the next time you get ambushed by her and beat her, Ceila will ask Linebeck what's up with her, and he explains something like this
"I was sailing through the ocean when i saw Jolene's ship being attacked by a monster, I ran my ship into it and she thanked me, we started sailing together as adventures but i got bored, and decided to part ways.. but stole some of her treasure, that's why she's chasing me"
^ not all that is word for word but you get the gist.
Then says that he accidentally crashed his boat into the monster while trying to escape
So from that you can kind of assume that Linebeck has always been in that Ocean, seeing as he and Jolene had sailed together in the past.
That's all I have though for his background.