You should always check for new rumors before speaking to the innkeeper;
this is indeed necessary for a lot of missions to appear.

But! After you complete the game, the game is not yet completed! You can
start a new game with your saved game from the completed game (still with me
on this? ;o)
New missions will appear and secret characters will offer to join your clan
(one tip: only accept one mission at a time; there is a bug that may make
you miss out on one secret character if you complete two certain missions at
the same time... You might read through some guides on GameFAQs for this).

Now for the secret part: for some secret missions to appear, you have to
CHECK CERTAIN MISSION ITEMS on the inventory screen (press start, choose
"clan" then "mission items" if I remember correctly). Some mission items
seem useless, but when bringing them along on missions you may make new
friends or new mission may appear in the Pub after examining them... I don't
really remember, but I think you can do this BEFORE completing the game. But
I could be wrong.

Phew...