Efficiently prime factorising an integer with an oracle
This does work (see the fundamental theorem of arithmetic), and is exactly how some efficient factoring algorithms work, such as Pollard-Brent. However they use a weaker oracle, one that just returns a factor, not necessarily a prime one.

Since Pollard-Brent (and maybe others) runs very slowly and/or not at all when passed a prime, there is often another specific prime check in place as well.

A proper recursive routine under those assumptions would be (in Python):

def factorize(n):
    if n == 1: return []
    if is_prime(n): return [n]
    f = one_factor(n)
    return factorize(f) + factorize(n//f)





  It seems pretty difficult to analyze. I think I would be able to come up with an expression in terms of the number of prime factors that the number originally has, but I can't seem to come up with an expression in terms of the number of binary digits.


Analyzing it in terms of the number of prime factors is exactly right. You can then get an upper bound on the number of binary digits by noting that a $b$-bit number may have at most $b-1$ prime factors.