I've just finished Locke's memories about his love in the city north of where Figaro castle pops up in the west.

Shadow is locateable... but I can't seem to hire him. (Yes I have three party members)