Stimmte denn die Ausgangsspeichenspannung des Laufradsatzes? Nicht selten wandern dabei die Speichen noch nen ganzen Milimeter in den Speichenkopf hinein (wenn man eine sinnvoll hohe Speichenspannung zugrunde legt - gerade am Tandem).
Allerdings wird das, so wie du das beschreibst, nicht viel bringen. Die Speichen sind wirklich deutlich zu kurz - gerade am Tandem kann das nicht lange halten.

Grundsätzlich bin ich beim Rad auch immer ein Freund des Selbsermachens. Bei meinen Solorädern halte ich das auch so, beim Tandemvorderrad würde ich das wahrscheinlich auch tun. Hinten ist das mit dem wahrscheinlich asymmetrischen Speichenstand aber eine Wissenschaft für sich. Wenn, dann würde ich das nur mit Tensiometer tun - und den habe ich nicht. Kurzum: Damit einen versierten Radhändler zu beauftragen ist sicher keine schlechte Idee. Zumindest was das Zentrieren betrifft. Vielleicht lässt sich der Händler darauf ein, dass du selbst aus- und einspeichst und er dann lediglich noch zentriert? Spart für den Händler Zeit und du lernst etwas und sparst vielleicht ein paar Kröten.

Was da so preislich zu veranlagen ist? Ich würde auf jeden Fall mit dreifach konifizierten Speichen (2,0/1,8/2,0) einspeichen, wahrscheinlich also Sapim Race oder DT Competition. Beide sind günstig im Netz so ab 50ct zu bekommen - in silber, schwarz ist manchmal teurer. Wenn du unbedingt auf nen verstärkten Speichenbogen wert legst, dann sowas wie die Alpine III. Je nach Speichenzahl brauchst du derer bis zu 80 Stück. Das sind die Materialkosten, wenn Felgen und Naben wiederverwendet werden können. Ach ja, bei Sapim sind meist Messingnippel dabei, eventuell kommen die aber noch dazu (wenn die bisherigen nicht verwendet werden sollen).
Zur Arbeitszeit: Eine ganze Stunde pro Laufrad halte ich für ne Fachwerkstatt für zu hoch angesetzt. Das muss etwas schneller gehen. Ne halbe Stunde dauert das aber bestimmt.