How to prevent the user profile page of a blocked user to show up? When a user is blocked the (core) user profile is still accessible. I would rather show a message "this user profile has been removed".

I could write an exception into the user-profile.tpl.php. Is there a better way?
You should be able to implement hook_user_view in a custom module.

First create a page which contains your preferred content (e.g. "This user profile has been removed").  Let's call this node/1337 for now.

Secondly, you want something along the lines of the following:

function mymodule_user_view($account, $view_mode, $langcode) {
  if ($account-&gt;status == '0') {
    drupal_goto('node/1337');
  }
}


There are other parameters you can pass to drupal_goto if you wish (such as HTTP response code) - check out the API for more info :-)