After upvoting and seconding "Hollowdead" and Alexandre E's answers (and various comments)... One might continue further on the idea that the alleged distinction between "mathematics" and "physics" is more a collection of conventions, artifacts of universities' development, artifacts of the human impulse to "classify", and so on. Another peculiar element that seems to have driven the "need" to distinguish these subjects is the modern-times mathematical fixation on a certain style of "proof" (despite the actual importance of heuristics, e.g., from physics) as the sine-qua-non of "mathematics". Thus, heuristic arguments/computations in physics often don't "qualify" as "mathematics" ... even while in the best-case scenarios Witten and other "physicists" have been led to suspect that proof-defined mathematics could proceed in a certain way which proved fruitful.
My own perception of my own "intuition" for mathematics is that it is "physical" in an informal sense, even on topics that are not part of the physics canon, nor "mechanics", nor... For me, this "physicality" includes many topics in "number theory" or "Galois theory" or "linear algebra" that are sometimes counted as "abstract mathematics" rather than "physical reality", although I disagree with the claims that this is "abstract".
Yes, of course, it is possible to employ a narrative style that specifically disassociates itself from "physical intuition", and there were historical motivations for at least setting up the possibility of reasoning that did not depend on "physicality", since some incorrect conclusions were reached by relying on "physical intuition" in situations that stretched our/human limitations a bit too far.
Another notion (which I do partly endorse) is that, since humans (and aliens) are in the physical world, the notion that mathematics (or anything else) would/could completely transcend or disconnect from this world seem unlikely, or pointless, or tautologically impossible, depending...
And there is the "false coincidence" pseudo-paradox notion: we do not notice cases that X is irrelevant to Y, nor remark upon it. :)
Thus, one way or another, I do think that the "suprising effectiveness of physics in mathematics" is due to a misrepresentation of the underlying ideas, and artificial stylization and compartmentalization of the official subjects, together with a not-so-unusual coincidence-fallacy amplifying it all.