In SS 3.3 it seem impossible to do this:

<?php

class Listing_FrontEndRequiredField extends RequiredFields
{

    //......

    public function php($data)
    {
        $valid = parent::php($data);
        //......
                                $this->validationError(
                                    'A listing with this name already exists, please <a href="'.$otherListing->Link().'">edit existing listing</a>.'
        //......
        //......
    }

    //......

}

Any ideas / hacks I can use to have the link show as a link rather than an escaped link.

Looks like in Form::Validate() the message is converted. ~#1312

$error['message'] = Convert::raw2xml($error['message']);

If you comment this line, it should work. Note to others reading this: not advisable, but overridable in some safe way I guess :)