How about something like:
(defun f-r-n (filename &optional directory)
(let* ((dir (if directory (expand-file-name directory) default-directory))
(file (expand-file-name (file-name-directory filename)))
(hf (find-file-name-handler file 'file-relative-name))
(hd (find-file-name-handler dir 'file-relative-name)))
(cond
((not (eq hf hd))
;; `filename' and `directory' are on different drives:
;; there is hence no relative name from `directory' to `filename'.
(expand-file-name filename))
((null hf)
;; Both are plain local: use the builtin code.
(file-relative-name filename directory))
((let ((re (car (rassq hf file-name-handler-alist))))
(equal (and (string-match re file) (substring file 0 (match-end 0)))
(and (string-match re dir) (substring dir 0 (match-end 0)))))
;; Both are non-local, use the same handler and same drive name.
(file-relative-name filename directory))
(t
;; Both are non-local and on different drives.
(expand-file-name filename)))))
Note how I check the handler for (file-name-directory filename) rather
than for `filename' so as to avoid uselessly catching jka-compr-style
handlers.
Stefan