Note: one need to be careful when working in spherical coordinates, as there are two conventions used for the notation of the polar and azimuthal angles. See https://en.wikipedia.org/wiki/Spherical_coordinate_system and the 2 pictures near the top. In this answer I am using the physicist's convention, since it complies better with your own notation.
To clear the first point of confusion: All vectors start at the origin. They can be added together visually by placing them head to tail, but you should always think of them as having the tail at the origin and the head pointing in whatever direction it's supposed to.
The cross product in rectangular coordinates and the cross product in spherical coordinates are the same thing. The only difference is the way we represent them in formulas.
Notation also seems to be confusing you. The basis in spherical coordinates works differently from the basis in rectangular coordinates. See http://mathworld.wolfram.com/SphericalCoordinates.html and scroll down to the listing of unit vectors for a complete account. Caution: This article uses the mathematician's notation. You will have to swap the roles of $\theta$ and $\phi$ in your head, or just write things down to keep track. e.g. $\hat{\phi}$ there is what we'll think of as $\vec{e}_\theta$.
Here is a working definition of the cross product:
The cross product of two vectors $\vec{a}$ and $\vec{b}$ is another vector, mutually perpendicular to $\vec{a}$ and $\vec{b}$, with the direction determined by the right-hand rule. The magnitude of $\vec{a}\times\vec{b}$ is given by the area of the parallelogram spanned by $\vec{a}$ and $\vec{b}$.
Note that this definition makes no reference to the choice of coordinate system; it works in rectangular and spherical coordinates.
Therefore, if $\vec{a} = (a,\theta,\phi)$ and $\vec{b} = (b,0,0)$ in spherical coordinates, to find the cross product we need to find the direction the vector is pointing and the magnitude from this information. The key to this is to find the angle between $\vec{a}$ and $\vec{b}$. Well, $\vec{b}$ points straight along the $z$-axis, so it suffices to find the angle of $\vec{a}$ relative to the $z$-axis, and if you draw a picture you should see that this angle is $\theta$. (It doesn't matter what $\phi$ is here.) The area of the parallelogram spanned by $\vec{a}$ and $\vec{b}$ is then $ab\sin\theta$. As for the direction, to be perpendicular to the $z$-axis the vector must lie in the $xy$-plane, so we need to find the direction in the $xy$-plane perpendicular to $(a,\theta,\phi)$. Then it suffices to find the direction perpendicular to $(1,\pi/2,\phi)$, which is of course $(1,\pi/2,\phi\pm\pi/2)$. The right-hand rule says we take the minus sign, so
$$
\vec{a}\times\vec{b} = ab\sin\theta(1,\pi/2,\phi-\pi/2).
$$
We can take the plus sign by pointing in the opposite direction, so
$$
\vec{a}\times\vec{b} = -ab\sin\theta(1,\pi/2,\phi+\pi/2).
$$
Finally, let's express the last vector in rectangular coordinates. It is
$$
(1,\pi/2,\phi+\pi/2)_{\text{sph}} = (\sin(\pi/2)\cos(\phi+\pi/2),\sin(\phi+\pi/2)\sin(\pi/2), \cos(\pi/2))_{\text{rec}} = (-\sin\phi,\cos\phi,0)_{\text{rec}} = \vec{e}_{\phi}
$$
according to the definition of unit vectors in spherical coordinates. (See the mathworld link above if you haven't already.) Therefore we finally obtain
$$
\vec{a}\times\vec{b} = -ab\sin\theta\vec{e}_\phi
$$
as claimed.
Now to compute $\vec{a}\times\vec{a}\times\vec{b}$, we know that $\vec{a}$ and $\vec{a}\times\vec{b}$ are perpendicular, so they span a rectangle. Therefore the area they span is the product of their lengths, or $a^2b\sin\theta$. (And there is a minus sign from the previous computation.) For the direction we need to compute
$$
\frac{\vec{a}}{\|\vec{a}\|}\times\vec{e}_{\phi}.
$$
$\vec{e}_\phi$ is the vector lying in the $xy$-plane perpendicular to $(1,\pi/2,\phi)_{\text{rec}}$. To be perpendicular to this and $\vec{a}$, we must find the vector in the plane perpendicular to $\vec{e}_\phi$ which, if you draw a picture, you'll see is the one containing $\vec{a}$ and the $z$-axis. Therefore to find the perpendicular we just have to shift $\theta$ by $-\pi/2$ (the sign comes from the right-hand rule). Therefore
$$
\frac{\vec{a}}{\|\vec{a}\|}\times\vec{e}_{\phi} = (1,\theta-\pi/2,\phi)_{\text{sph}}
$$
and if we work this out in rectangular coordinates,
$$
(1,\theta-\pi/2,\phi)_{\text{sph}} = (\sin(\theta-\pi/2)\cos\phi,\sin(\theta-\pi/2)\sin\phi,\cos(\theta-\pi/2))_{\text{rec}} = (-\cos\theta\cos\phi,-\cos\theta\sin\phi,-\sin\theta)_{\text{rec}} = -\vec{e}_\theta.
$$
So putting everything together,
$$
\vec{a}\times\vec{a}\times\vec{b} = -a^2b\sin\theta(-\vec{e}_\theta) = a^2b\sin\theta\vec{e}_\theta.
$$
This is never zero except in the following cases (which are not mutually exclusive): if $\vec{a}=0$, if $\vec{b}=0$, or if $\vec{a}$ and $\vec{b}$ point in the same or opposite directions (so that $\sin\theta=0$). Which you could guess from the original working definition of the cross product: since $\vec{a}\times\vec{b}$ always points perpendicular to $\vec{a}$, as long as we don't have some trivial case the vectors $\vec{a}$ and $\vec{a}\times\vec{b}$ will span a parallelogram of nonzero area.
As you can see, this whole business with spherical coordinates is rather cumbersome for the cross product. This is because the cross product is designed to respect linear combinations, and therefore it works well in a rectangular system where the local geometry looks the same everywhere. However, in curvilinear coordinates (like spherical), vectors do not add coordinatewise like in rectangular coordinates, so the cross product cannot use the special linear structure of $\mathbb{R}^3$. The easiest way to do things is to learn to break up vectors into the local basis for spherical coordinates, and learn the formulas for the cross product of the local orthonormal basis in spherical coordinates. Either that, or as Griffiths suggests in Introduction to Electrodynamics, just convert to rectangular coordinates and try to do most things there.
Best Answer
Here are two ways to derive the formula for the dot product. I assume that $v_1$ and $v_2$ are vectors with spherical coordinates $(r_1, \varphi_1, \theta_1)$ and $(r_2, \varphi_2, \theta_2)$.
First way: Let us convert these spherical coordinates to Cartesian ones. For the first point we get Cartesian coordinates $(x_1, y_1, z_1)$ like this: $$ \begin{array}{rcl} x_1 & = & r_1 \sin \varphi_1 \cos \theta_1, \\ y_1 & = & r_1 \sin \varphi_1 \sin \theta_1, \\ z_1 & = & r_1 \cos \varphi_1. \end{array} $$ Similar formulas hold for $(x_2, y_2, z_2)$. Now, the dot product is simply equal to $$ (v_1, v_2) = x_1 x_2 + y_1 y_2 + z_1 z_2 = \\ = r_1 r_2 ( \sin \varphi_1 \sin \varphi_2 ( \cos \theta_1 \cos \theta_2 + \sin \theta_1 \sin \theta_2) + \cos \varphi_1 \cos \varphi_2) = \\ = r_1 r_2 ( \sin \varphi_1 \sin \varphi_2 \cos (\theta_1 - \theta_2) + \cos \varphi_1 \cos \varphi_2) $$
Second way: Actually, we could have done it without coordinate conversions at all. Indeed, we know that $(v_1, v_2) = r_1 r_2 \cos \alpha$, where $\alpha$ is the angle between $v_1$ and $v_2$. But $\cos \alpha$ can be immediately found by the Spherical law of cosines, which yields exactly the same formula that we just proved. Basically, our first way is itself a proof for the spherical law of cosines.
PS: I'm not saying anything about cross products, but my guess is that the correct formula will look terrible. Not only will it contain sines and cosines, it is likely that it will also contain arc functions (they will appear when we try to convert the result back to spherical coordinates). Unless those arc functions magically cancel out with all the sines and cosines. But it is highly unlikely, and I don't feel like going through the trouble of checking.
PPS: One more thing. Cross products are not the only scary thing about spherical coordinates. If you think about it, even addition of two vectors is extremely unpleasant in spherical coordinates. Multiplication by a number is alright though, because it only changes $r$ and doesn't affect $\varphi$ and $\theta$ (at least when we multiply by a positive number).