I should think Belthasar came to the eleventh century and contacted Lucca, telling her about Project Kid. He would then use Lucca's connections with Luccia to get him a job as the Viper Manor librarian, thus earning him a good spot to oversee the completion of Project Kid.
As for Terra Tower... The most reasonble answer I can come up with is he used magic to create an illuision of the library in Viper Manor... Hmm, let's see, he called the library in the tower... ~Checks Chrono Cross script~
Ah, a "space that does not exist". Yes, I guess an illusion can go under that kind of description. Anyway, he created it so Serge can find something familiar in the Tower, so he could tell him about Terra Tower, the Dragon God and FATE in somewhat more comfortable circumstances. You then leave the library, and it's as good as gone. And, after defeating the Dragon God\TimeDevourer Belthasar gives you the Time Egg and disappears completly off the face of the archipelago.
As for Home World... I guess he fled with the Neo Epoch when the Manor got wrecked. Or, if my theory is correct and Lucca wasn't kidnapped in Home World, he went to Zenan so the two can further oversee the operation.