Just so this is complete:
I didn't know about the possibility of shipping out of PT. Klang and so took the little detour described above.Shipped it, like everyone, with Cakra, contact data see here
. Highly pleased with the service and the folks in Penang. The only little thing was that I couldn't be there while loading cause Friday was a holiday, but I guess that's not really a sensible point on the con-list.
If you are not as dumb as I am you can take one of two daily AirAsia flights to Medan for only 129 MYR including everything.
The other option is Port Klang, BUT instead of taking the Dumai bound ferry there is a second Ferry going to Tanjung Balai, no visa on arrival, though the 1-month Visa is even more of a joke than the 2-month one. This cuts your Bus-Time in Sumatra from near 20h to 4h. They are not used to foreigners taking that route I think as everyone from customs officer to daily users was very interested (starring). It was crowded as hell that day, delayed by around 3 hours and so full, people had to wait on the outside deck. Customs was a mess as everything was done in the ship and took ages. Though I was told it's usually way less crowded, just the holiday playing me again. To get from there to Medan you either take a share taxi or the train.
Private cars go for 200.000 Rp, at least I was told so by a friendly local working in KL and speaking English sharing the taxi with me and explaining and helping me loads (yes, shitluck), might even go cheaper. But for a 4 hour ride I considered it OK. So if you're more than 3 people it's pretty much a nice deal. If you're alone it's a little ruff.
I later was told in Medan there are also trains running for 10.000 Rp. I did neither see a train station nor did it look like there'd be one, but Lonely Planet says the same. 2 daily trains, no idea about the times.
There's also supposed to be a hotel in town somewhere the custom guys told me.
In Belawan the agent was a dick. Tried to overcharge me on official fees and was still sleeping when I called, after finding the closed office, at 9am and told me to wait 2-3 hours. Again it's Ramadan, and so this might be a bad day, but still, I got pretty pissed after getting up at 6.30 myself to get out there in time. After I told him I'm going to the customs myself he magically appeared within 30 minutes.
So for all: Official Harbour-Fee is 800.000 Rp, at least the main customs office and Cakra told me so. He tried a million first, wanted 900.000 for 20 Minutes, he even called Cakra who told me not to pay so he gave up after a little more.
The customguys were great, fast and friendly.
Hope it helps.