Hmm, maybe your sendmail just doesn't like the '-f' option -- the
comment in message.el suggests that this is sometimes the case:

;; Always specify who from,
;; since some systems have broken sendmails.
;; But some systems are more broken with -f, so
;; we'll let users override this.

Does '-f' work if you use sendmail from the command line?