for those interested, the process is like this:
Make contact with Inschape Shipping in Alexandria (Their agents according the the Vicemar Website) at least 24 hours before departure.
Then one of their agents will meet you at the port entrance 11 hours before the ship is due to sail. From there it is pretty much a question of sitting back, relaxing, making tea and watching egypt at work at a very slow pace... Nothing to it and everything happens around you.
It cost me 98 Egyptian pounds in total of which 91 was a fine for overstaying my customs paperwork by three weeks. At the time I was travelling there was no police in Egypt (Due to revolution) so I did not even have a Traffic Court visit before leaving.