Yeah, I figure there must be some kind of ritual or magic that allows the remains to be tracked down. Though that raises the question of why the Belmont's never try to track down the remains themselves to try and preemptively destroy them.
On another tangent, I always thought that they missed a trick in Harmony of Dissonance by not making Maxim Mode a 'prequel' to the main game, with Maxim tracking down Dracula's remains. Of course, by the nature of being an alternate mode it would have all had to take place within the castle from HoD so that may not have ultimately made much sense.
Hang on though, Juste does find Dracula's remains in the HoD Castle, which means Maxim already brought them there beforehand. That or the Castle with the remains materialised prior, but I'm sure Maxim states that he'd found the remains. (see his quote below). Since Maxim and Dark Maxim speak repeatedly on Dracula's remains, I assumed Maxim collected the remains in Wallachia (mansions, countryside, etc and whereever) and brought them to the Castle himself. Maxim was indeed influenced by the power of the remains and Good Maxim at one point says to Juste:
Maxim: "Dracula's strength was so overwhelming"
Lydie was going to be the final sacrifice that merged the two Castles, and reinforce Dark Maxim's power according to Death:
Death: "He was born of my Lord, so of course he knows ways to reinforce his power."
Juste: "?! No, surely not... Lydie's blood.."
Death: "That Maiden will play an essential role in the completion of this castle."
Therefore, the remains' influence (Dracula's power) found a host (Maxim) who found a blood sacrifice (Lydie).
As to why the remains were spread throughout the Castle, I assume that either Dark Maxim did this to hamper Juste's quest (from entering the final chamber in Castle B) as they were no longer required. (It's not the same situation as CVII where they were being guarded in the mansions and Simon required Oak Stakes to break the seal upon them.) When Dark Maxim tears away from Good Maxim, the remains unknowingly would resonate with him, creating 'Dracula Wraith'.