To expand upon what Iku said; it is possible, assuming stable warp conditions, a "straight line" course, no major crew casualties (psychological, psychic, or physical), no serious equipment malfunctions and a sufficiently hardcore Navigator (or team thereof) for an Imperial ship to travel from one end of the galaxy to the other in a year (see either the original Warhammer 40,000: Rogue Trader core book, or Space Fleet. Can't quote page references offhand, I'm afraid).
In practical terms, a year at warp isn't going to happen. Equipment will break down if it's put under high levels of stress for that long (and you do not want that to happen to the Geller Field Generators), and unless you manage to get a crew of perfectly, superhumanly sane and stable Untouchables/pariahs, spending such a prolonged period out on the Sea of Souls is going to result in a significant portion of the crew getting warp-crazed, or rioting or even getting possessed. All Very Bad Things ™.
Added to that the fact that it's apparently nearly impossible to use the Empyrean near the galactic core (See Fanatic! Mag #2), so you'd need to take a rather significant dog-leg, which would necessarily increase the time spent out of Real space. Obviously, this would exacerbate other problems.
Also worth bearing in mind is that even Navigators have to take breaks, and for that matter, return to real space to fix their position via star sightings periodically. This is why journeys tend to take longer- ships drop back into real space, do maintainance, figure out where they are, recalculate their course for the next leg and, if possible, dock/put in for supplies (they may not be needed, but it's good practice).
To put it into context, a trip from Eechan in the Helican sub, Scarus Sector to Cadia (the next sector across, possibly the next-but-one) took Inq. Eisenhorn the best part of a year, but that required changing vessels part-way, and most of the distance was done on a Mechanicus super-heavy transport, which is admittedly not the fastest of ships. Inq. Draco, on the other hand, managed to make the trip from Stalinvast, to the Eye, to Holy Terra (a trip far more hazardous, and several dozen times the length) in roughly twice as long, although his ship was his own (rather than havine to book passage on other vessels), and built to be fast, discreet and very, very cool.
A century later, Draco and his entourage travel from Terra out past Kar Duniash (so, given the need for the dogleg, a trip of roughly the same distance as the galaxy edge-to-edge), with a few stops along the way, in roughly 2-4 years or so. Again, fast ship, but still: totally possible for characters from all over the Imperium to wind up together, particularly if you're not too bothered about them being roughly the same age- lots of warp travel makes it kinda tricky to determine someone's actual age anyway (is it how long they've lived/experienced? or how long since they were born?).
To look at your specific examples- Praetoria and Valhalla are, I believe, part of the same Segmentum, so having the noble pick up the Guardsman isn't that far-fetched (admittedly, even a Sector is massive in actual terms, never mind a Segmentum). It does suggest their route towards the Expanse, though: Praetoria is quite a way Coreward-by-Spinward of Valhalla, and they're both on the other side of the galaxy from Glavia (which actually isn't that far from the Koronus Expanse, comparatively speaking. It's only a couple of Sectors over, in Scarus). So, either the Glavian is doing the galactic tour, or he's the last one they pick up (which suggests they were passengers on someone else's ship, if not several in succession on the way there, which kind of works better, in my conception of 40k fluff, at least). If the latter, then the Praetorian is likely headed Rimward-by-Trailing out to Kar Duniash (logical point to meet the Valhallan, as it's the Segmentum capital. Major transhipment hub, headquarters of the Administratum and the Guard and Navy for the whole Segmentum), and then taking a Trailing route to the galactic North, past Valhalla (other possible meeting point) to Dimmamar just across the border in the Segmentum Tempestus, and then either carry on straight Trailing to Cypra Mundi (another Segmentum capital), or beat Coreward to Ornsworld. From that point, it gets complicated as both routes then have to deal with outlier storms from the Eye, but it's also far more populated. The Ornsworld route makes a bit more sense though, as it allows an easier passage up to the Cadian sector, and then they can beat along around to the Scarus, and then Calixis sectors, and obviously, from there the Koronus Expanse awaits.