Ok...wenn ich es richtig verstehe, gibt also keinen bestimmten Grund für die Strecke Nong Khai - Mukdahan...
Dann würde ich doch erst einmal die "Standard-Strecke" auf dem Mekong empfehlen: 2 Tage von Huay Xai (= Chiang Khong auf Thai-Seite) nach Luang Prabang in Laos. Hier gibt es die "normale" Option mit einem der Slowboats oder auch die kreuzfahrtähnliche Variante mit einem Luxus-Schiff (mir fällt der Name des Schiffs gerade nicht ein...). Das ist eine sehr schöne Landschaft und ein Schiff zu bekommen ist gar kein Problem - ist eine echte "Rennstrecke". Je nach Jahreszeit kann die Fahrt mit dem Slowboat entweder angenehm (wenn auch immer spartanisch) oder schrecklich vollgestopft (d.h. Dutzende von Backbackern, bis das Boot voll ist) sein. Eventuell wäre daher die Gegenrichtung eine Option, da die meisten den Mekong runter und nicht rauf fahren... Das Ziel Luang Prabang ist auf jeden Fall zu empfehlen. Wer etwas von Laos sehen möchte, kommt an LP eigentlich nicht vorbei.
Von LP aus kann man wohl auch in 3 bis 4 Tagen bis Vientiane fahren. Offizielle Preise sind angeschrieben. Ich weiß aber nicht, wie oft dort tatsächlich Boote fahren. Aber es sollte sicher machbar sein (und wenn ernstes Interesse daran besteht, kann ich da sicher noch genauerer Infos bekommen). Auch von Pakse bis (fast) zur kambodschanischen Grenze (wieder komplett in Laos) sollte es wieder möglich sein, Boote zu bekommen.
Wenn es nun nicht unbedingt der Mekong selbst sein muss, empfinde ich als schönste Flussfahrt in der Gegend auf jeden Fall von Luang Prabang aus die Fahrt (zunächst auf dem Mekong und dann) auf dem Nam Ou empfehlen. Die 2 Tage flußaufwärts gehören wirklich zu den Highlights in dieser Gegend. Allerdings ist das nicht ganz so preiswert, da man in LP ein eigenes Boot organisieren muss. Aber für 2 oder gar 4 Personen ist das ok und auf jeden Fall den Preis wert.