I believe most era I express steam loco would do. From the Märklin catalog, a S3/6 or a Wurt C would be fine and may actually be the only Märklins that would fit.

The beautiful era I Wurt K would look fantastic too, but would be totally unsuitable, since it's a very slow freight lok.

If you choose other brands (Gutzold, Lilliput, etc), I would feel that the excellent BR 19.0 or BR 18.5 available would be superb too. I just don't remember the correct era I designation of these two, so I used the era II designations instead.

Luis

So basically you are saying that as the Orient Express passed into a new country a new loco was attached to the front? I always assumed the same loco was used for the whole journey...

Ah yes, I have one, in the DRG BR 16 version and it's a absolutely superb model, extremely beautiful, quite silent and powerful.

Evidently it sheds parts along the track (really!), and is pushed around by its tender. Still, I bought it due to its beautiful looks.

In its era I austrian version (which has even more details than the era II DRG BR 16) it would be an awesome sight pulling your extraordinarily beautiful luxuszug (I thought about getting one on ebay, but it's quite expensive!) Congrats on your set!

Luis

Hi all,

Pretty much of the topic is covered already, I only miss one option. The KPEV S10 (or BR 19) is also an interesting loco to go with this wonderful set. Only problem: the "real" era I KPEV version is only produced as a part of the 2681/2881 Wilhelm Zug set. However, it's possible to buy the loco separately. (It's even boxed separately, due to the spread delivery of the complete set a few years ago.) Another not completely prototypical version is the BR 17 version (37192) which has the DRG texts on it but is still in the era I (green) color. This loco might be a great alternative to the S3/6. (Also a nice model by the way.)

Overall, I would go for:
S10 ref. 2681/2881
S10 BR 17 ref. 37192
S3/6 green ref. 37181/33181
S3/6 yellow ref. 37185/33185 (there's some doubt about the prototypically color, there has been a S 3/6 in that color, a special for a demonstration purpose and I'm not sure whether it has really pulled trains or has been recolored before regular operation)
Würt C blue ref. 3511/3611
Würt C black ref. 3514/3614 (it's the era I version.)
Würt C green ref. 37113

Since I own pretty much all models discussed in my reply (including the 42754 set) my personal favourite would be the 2681 (but the 37192 looks almost just as nicely and has improved running characteristics) or the black Württemberger C. I think the yellow S 3/6 would look great to, however, I'm not sure about the prototypicallity of this loco.
Ah... actually they're all great!