How does Drupal select default domain for relative links?
You can specify the domain in settings.php - it's the variable called $base_url (around line 271). It is not always necessary, but I've found it can prevent some unexpected errors if the domain is set explicitly. I'm not sure how Drupal decides the domain if the $base_url is not set. By default, the $base_url is commented out. To set it, remove the # in front and change www.example.com to your primary domain.

Are the links in the block built using a Drupal menu? I think when you set the leading slash, you actually circumvented Drupal's menu handling which is probably why it worked. If you set the $base_url, I think you could remove the leading slashes from the links.