Reimplementation of `called-interactively-p` in pure elisp, with bugfixes. Try running this file with `emacs -Q -batch -f toggle-debug-on-error -l interactive-p-reimplementation.el`. You should get no errors, but 3 warnings about cases that the built-in `called-interactively-p` gets wrong but my implementation gets right.

interactive-p-reimplementation.el

(require 'cl)

(defsubst my-interactive-internal ()
  "Eqivalent of the INTERACTIVE macro in the Emacs C source.

This should never be called directly."
  (and (not executing-kbd-macro) (not noninteractive)))

(defun backtrace-from (fun)
  "Return all backtrace frames, starting with the one for FUN.

FUN may be a list of functions, in which case the first one found
on the stack will be used."
  (let ((stack (macroexp--backtrace))
        (funcs (if (functionp fun)
                   (list fun)
                 fun)))
    (while (and stack 
                (not (memq (cadar stack) funcs)))
      (setq stack (cdr stack)))
    stack))

(defun clean-advice-from-backtrace (stack) 
  (let ((skipping-until nil))
    (loop for frame in stack
          for func = (cadr frame)
          ;; Check if we found the frame we we're skipping to
          if (and skipping-until 
                  (eq func skipping-until))
          do (setq skipping-until nil)
          ;; If we're looking at an the original form of an advised
          ;; function, skip until the real name.
          if (and (not skipping-until)
                  (looks-like-advised-orig func))
          do (setq skipping-until 
                   (intern 
                    (substring (symbol-name func) 
                               (eval-when-compile (length "ad-Orig-")))))
          unless skipping-until collect frame)))

(defsubst looks-like-advised-orig (func) 
  "Returns t if FUNC is a symbol starting with \"ad-Orig-\".

Such symbols are used to store the original definitions of
functions that have been advised by `defadvice' or similar."
  (and (symbolp func)
       (string-prefix-p "ad-Orig-" (symbol-name func))))
(defsubst looks-like-call-interactively (func)
  "Returns t if FUNC looks like the function `call-interactively'.

FUNC \"looks like\" `call-interactively' if it is the literal
symbol `call-interactively', or the value of `(symbol-function 'call-interactively)', or a symbol whose `symbol-function' is the same as that of `call-interactively'."
  (eq (symbol-function 'call-interactively)
      (if (symbolp func)
          (symbol-function func)
        func)))

(defun my-interactive-p-internal ()
  "Equivalent of C function \"interactive_p\". 

This should never be called directly."
  (let ((stack 
         (clean-advice-from-backtrace
          (cdr 
           (backtrace-from '(my-called-interactively-p my-interactive-p))))))
    ;; If we're running an Emacs 18-style byte-compiled function,
    ;; there may be a frame for Fbytecode at the top level.  In any
    ;; version of Emacs there can be Fbytecode frames for
    ;; subexpressions evaluated inside catch and condition-case.  Skip
    ;; past them.

    ;; If this isn't a byte-compiled function, then we may now be
    ;; looking at several frames for special forms.  Skip past them.

    ;; Also skip any frames that look like the original forms of
    ;; advised functions
    (while (and stack
                (or (eq (cadar stack) 'bytecode)
                    (null (caar stack))
                    (looks-like-advised-orig (cadar stack))))
      (setq stack (cdr stack)))
    ;; Top of stack is now the function that we want to know
    ;; about. Pop it, then check if
    ;; the remaining top of the stack is `call-interactively'.
    (looks-like-call-interactively (cadadr stack))))

(defun my-interactive-p ()
  "Reimplementation of `interactive-p'."
  (and (my-interactive-internal)
       (my-interactive-p-internal)))

(defun my-called-interactively-p (&optional kind)
  "Reimplementation of `called-interactively-p'."
  (and (or (my-interactive-internal)
           (not (eq kind 'interactive)))
       (my-interactive-p-internal)))

;; All of the following should work
(defun must-be-interactive ()
  (interactive)
  (if (my-called-interactively-p)
      (progn 
        (unless (called-interactively-p)
          (warn "`called-interactively-p' got this one wrong."))
        t)
    (error "Must be interactive!")))
;; Should work
(call-interactively 'must-be-interactive)

;; Should fail
(funcall (symbol-function 'call-interactively) 'must-be-interactive)

(fset 'call-interactively-alternate-name (symbol-function 'call-interactively))

;; Should fail
(call-interactively-alternate-name 'must-be-interactive)

(defadvice call-interactively (around no-op activate)
  "Does nothing, just runs `call-interactively' as normal."
  ad-do-it)

;; Should fail
(call-interactively 'must-be-interactive)

Interesting. I didn't know Elisp had the facilities for inspecting the call stack like this.

What version of emacs are you using? GNU Emacs switched to an elisp-based implementation of called-interactively-p in 24.4, about a year ago, so it's probably interesting to compare the two.