redirect

Unless you are spending a great deal of time worrying about what search engines do, I wouldn't go for users clicking. It's just an annoyance for them. If you have a very high traffic site, then you may need to worry about that. However, actually getting high in search engine ranking is extremely difficult and expensive.

You mentioned that numerous people link from other sites... which means that they will be using the GET method, and hence not HEAD.

The specification states:

10.3.2 301 Moved Permanently

The requested resource has been assigned a new permanent URI and any future references to this resource SHOULD use one of the returned URIs. Clients with link editing capabilities ought to automatically re-link references to the Request-URI to one or more of the new references returned by the server, where possible. This response is cacheable unless indicated otherwise.

The new permanent URI SHOULD be given by the Location field in the response. Unless the request method was HEAD, the entity of the response SHOULD contain a short hypertext note with a hyperlink to the new URI(s).

If the 301 status code is received in response to a request other than GET or HEAD, the user agent MUST NOT automatically redirect the request unless it can be confirmed by the user, since this might change the conditions under which the request was issued.

      Note: When automatically redirecting a POST request after
      receiving a 301 status code, some existing HTTP/1.0 user agents
      will erroneously change it into a GET request.

(http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html)

Which would mean that you should be using a page where the user must click. This is simply a pain for users and who cares about the specification anyways?

To determine whether to use sexy redirection or 301 redirection, you need to know where your traffic comes from. If it is search engines, then perhaps.

Google, Yahoo, and MSN all work fine with server-side redirection and do not ban sites for it.