Concerning the first question:
The field values of a profile list are run through ´check_plain() in
profile_view_field()`, so you can only get markup in there after they got loaded, which leaves you with at least two options, depending on where you want to alter the output:
Implement hook_user()
and, on the 'view' operation, modify the field values in the $account->content array (Make sure that your modules weight is below that of the profile module or the values will not be in there yet).
Add your own preprocess functions for all templates where the fields are used and make your adjustments there. On first sight, these should be the following, but the list might be incomplete:
yourModule_preprocess_profile_block()
(profile module)
yourModule_preprocess_profile_listing()
(profile module)
yourModule_preprocess_user_profile_item()
(user module)
As for the second question:
Also, when using l(), is there a way
to say: create a link to the node with
$nid, no matter where it happens to be
located at runtime?
I do not understand what you mean by "no matter where it happens to be located at runtime". Anything that is not covered by the following?
l('SomeTitle', 'node/' . $nid)