Mathematicians' Tensors vs. Physicists' Tensors
Solution 1:
What a physicist probably means when they say "tensor" is "a global section of a tensor bundle." I'll try and break it down to show the connection to what mathematicians mean by tensor.
Physicists always have a manifold $M$ lying around. In classical mechanics or quantum mechanics, this manifold $M$ is usually flat spacetime, mathematically $\mathbb{R}^4$. In general relativity, $M$ is the spacetime manifold whose geometry is governed by Einstein's equations.
Now, with this underlying manifold $M$ we can discuss what it means to have a vector field on $M$. Manifolds are locally euclidean, so we know what tangent vector means locally on $M$. The question is, how do you make sense of a vector field globally? The answer is, you specify an open cover of $M$ by coordinate patches, say $\{U_\alpha\}$, and you specify vector fields $V_\alpha=(V_\alpha)^i\frac{\partial}{\partial x^i}$ defined locally on each $U_\alpha$. Finally, you need to ensure that on the overlaps $U_\alpha \cap U_\beta$ that $V_\alpha$ "agrees" with $V_\beta$. When you take a course in differential geometry, you study vector fields and you show that the proper way to patch them together is via the following relation on their components: $$ (V_\alpha)^i = \frac{\partial x^i}{\partial y^j} (V_\beta)^j $$ (here, Einstein summation notation is used, and $y^j$ are coordinates on $U_\beta$). With this definition, one can define a vector bundle $TM$ over $M$, which should be thought of as the union of tangent spaces at each point. The compatibility relation above translates to saying that there is a well-defined global section $V$ of $TM$. So, when a physicist says "this transforms like this" they're implicitly saying "there is some well-defined global section of this bundle, and I'm making use of its compatibility with respect to different choices of coordinate charts for the manifold."
So what does this have to do with mathematical tensors? Well, given vector bundles $E$ and $F$ over $M$, one can form their tensor product bundle $E\otimes F$, which essentially is defined by $$ (E\otimes F)_p = \bigcup_{p\in M} E_p\otimes F_p $$ where the subscript $p$ indicates "take the fiber at $p$." Physicists in particular are interested in iterated tensor powers of $TM$ and its dual, $T^*M$. Whenever they write "the tensor $T^{ij...}_{k\ell...}$ transforms like so and so" they are talking about a global section $T$ of a tensor bundle $(TM)^{\otimes n} \otimes (T^*M)^{\otimes m}$ (where $n$ is the number of upper indices and $m$ is the number of lower indices) and they're making use of the well-definedness of the global section, just like for the vector field.
Edit: to directly answer your question about how they get their transformation rules, when studying differential geometry one learns how to take compatibility conditions from $TM$ and $T^*M$ and turn them into compatibility relations for tensor powers of these bundles, thus eliminating any guesswork as to how some tensor should "transform."
For more on this point of view, Lee's book on Smooth Manifolds would be a good place to start.
Solution 2:
Being a physicist by training maybe I can help.
The "physicist" definition of a vector you allude to, in more mathematicians-friendly terms would become something like
Let $V$ be a vector space and fix a reference frame $\mathcal{F}$ (mathematicians lingo: a basis.) A collection $\{v^1, \ldots, v^n\}$ of real numbers is called a vector if upon a change of reference frame $\mathcal{F}^\prime = R ^{-1} \mathcal{F}$ it becomes the collection $\{ v^{\prime 1}, \dots, v^{\prime n}\}$ where $v^{\prime i} =R^i_{\ j} v^j$.
If you like, you are defining a vector as an equivalence class of $n$-tuples of real numbers.
Yes, in many physics books most of what I wrote is tacitly implied/shrugged off as non-important. Anyway, the definition of tensors as collections of numbers transforming according to certain rules is not so esoteric/rare as far as I am aware, and as others have pointed out it's also how mathematicians thought about them back in the past.
Physicists often prefer to describe objects in what they find to be more intuitive and less abstract terms, and one of their strength is the ability to work with vaguely defined objects! (Yes, I consider it a strength and yes, it has its drawback and pitfalls, no need to start arguing about that).
The case of tensors is similar, just think of the collection of numbers with indices as the components with respect to some basis. Be warned that sometimes what a physicist calls a tensor is actually a tensor field.
As to why one would use the definition in terms of components rather than more elegant invariant ones: it takes less technology and is more down-to-earth then introducing a free module over a set and quotienting by an ideal.
Finally, regarding how to communicate with physicists: this has always been a struggle on both sides but
Many physicists, at least in the general relativity area, are familiar with the definition of a tensor in terms of multilinear maps. In fact, that is how they are defined in all GR books I have looked at (Carroll, Misner-Thorne-Wheeler, Hawking-Ellis, Wald).
It wouldn't hurt for you to get acquainted, if not proficient, with the index notation. It has its own strengths and is still intrinsic. See Wald or the first volume of Penrose-Rindler "Spinors and space-time" under abstract index notation for more on that.
Solution 3:
I had this exact discussion a few months ago in the comments of this answer on Academia.SE. Let me report here my argument, with a few additions.
Let's start with your first point:
It seems, at times, that physicists and mathematicians mean different things when they say the word "Tensor."
There's really no difference in the modern definitions of vectors and tensors in physics and mathematics. There was such a difference 50 or more years ago, but not really today. However, many old-school physicists still insist with the old point of view.
This does not really make any sense to me. Even for "Vectors" and before we get to "Tensors," it seems like we'd have to be given a sense of what it means for an object to "transform." How do they divine these transformation rules?
In the olden times physicists defined vectors and tensors as arrays of numbers which transformed in two possible ways under changes of the coordinate system. An example of such a definition can be found in E. Persico, Introduzione alla fisica matematica, p. 27 (pdf) from 1943. It's in Italian, but I think that the different mathematical approach with respect to modern books is evident (I chose this Italian book as example because I studied tensors on it some thirty-odd years ago, when I was 17, and I'm still fond of it). For a physicist, coordinate systems (which are pure mathematical objects) are associated to reference frames, that is, to physical operations that allow to associate coordinates with events. The transformation rules mentioned in your post are then those associated to a change of basis, in a vector space or its dual.
Of course, with such a definition, you don't go very far. Modern physics has a different approach: for instance, in Newtonian mechanics, the space-time is assumed to be an affine space with a certain structure (in relativity, one assumes a different structure). Vectors, then, are just the vectors of the vector space associated to this affine space, exactly as you would do in mathematics. A German physics book which adopts this approach is N. Straumann, Theoretische Mechanik. One about special relativity that adopts this modern view is E. Gourgoulhon, Special Relativity in General Frames.
In modern physics, tensors are defined as multilinear maps, showing that those old arrays of numbers were just the components of the tensor with respect to a certain base. And the transformation rules follow directly from this definition. There is probably still a difference with respect to the mathematical definition: in fact, tensors in algebra are defined as element of a tensor space which possesses a certain universal property, and multilinear maps are used in a constructive proof of the existence of a tensor space, but this is just one possible construction out of many others which are isomorphic. Physicists usually skip on this and define tensors as multilinear maps. I studied the modern approach already in 1997 during a relativity course, and the professor stressed several times that the old approach was outdated since long.