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->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 :-)
You can try to alter the page callback of user profile page, change the access callback to point to your custom function that determine whether a user is blocked.