A matrix algebra has no deformations? I have often heard the slogan that "a matrix algebra has no deformations," and I am trying to understand precisely what that means.  While I would be happy with more general statements about finite-dimensional semisimple algebras over non-necessarily algebraically closed fields, I am mainly interested in the case when the base field is $\mathbb{C}$, so the question is phrased in terms of matrix algebras over $\mathbb{C}$.  I will state the question in three different contexts, in increasing order of interest to me, and say what I know about each one.
Formal Deformations
A formal deformation of an associative $k$-algebra $A$ is a $k[[h]]$-bilinear multiplication on $A[[h]]$ of the form
$$ a \cdot b = ab + m_1(a,b)h + m_2(a,b)h^2 + \dots  $$
where the first term is given by the original multiplication on $A$.  This type of deformation is connected with the Hochschild cohomology $HH^\bullet(A)$.  As I understand it, for a semisimple algebra $A$, the Hochschild cohomology vanishes in degree $\ge 1$, and this implies that a matrix algebra has no deformations in the formal sense.  So I guess there isn't much of a question so far.
Deformation of Structure Constants
In this context, we fix a natural number $n$ and a vector space $V$ with a fixed basis $a_1, \dots, a_n$, and we consider associative algebra structures on $V$.  The structure constants of an algebra $A$ with underlying vector space $V$ with respect to this basis are the complex numbers $c_{ij}^k$ such that
$$ a_i a_j = \sum_{k}c_{ij}^k a_k,  $$
and these numbers clearly determine the algebra.  This gives us a point in $\mathbb{C}^{n^3}$.  Associativity gives us some polynomial constraints on the structure constants, so we can think of the collection of $n$-dimensional associative algebras as some kind of algebraic variety in $\mathbb{C}^{n^3}$.  (I know very little algebraic geometry, so please excuse/correct me if am using the wrong terminology.)  Since one can take many different bases for an algebra, this variety overcounts associative algebras.
I don't know how this is proved, but as I understand things, semisimplicity is a Zariski-open condition in the variety of associative algebra structures, so semisimplicity is preserved under small deformations, and so a small deformation of $M_n(\mathbb{C})$ is still semisimple.
Question 1

Is the property of being a matrix algebra preserved under deformation of structure constants?

Deformation of Relations
This is the most flexible setting, and the one in which I am most interested.  Here we consider algebras with a fixed collection of generators and a fixed number of relations, and we allow the relations to vary smoothly.  This allows the dimension of the algebra to vary as well.  However, this is also the hardest notion to formalize.
An example will illustrate what I mean.  Consider the family of algebras
$$ A_t = \mathbb{C}[x]/(tx^2 -x),$$
where $t$ varies in $\mathbb{C}$.  Clearly there is a drop in dimension at $t=0$, although generically the dimension is constant.  A slightly more complicated example is given by the family $B_t$, where 
$$ B_t = \mathbb{C} \langle x,y \mid x^2 = y^2 = 0, \quad xy + yx = 2t \rangle.$$
In this example the dimension is constant, but at $t=0$ one has the exterior algebra $\Lambda(\mathbb{C}^2)$, while for $t \neq 0$ this is the Clifford algebra of $\mathbb{C}^2$ with respect to a nondegenerate bilinear form, and hence $B_t \simeq M_2(\mathbb{C})$ for $t \neq 0$.
Question 2

What is a good way to formalize this notion of deformation?

A first guess would be something like this: fix a space of generators $V$, a number of relations $k$, and a base manifold $M$ (in my above examples $M=\mathbb{C}$).  To limit things a bit, I guess I would like to consider only quadratic-linear relations.  Allowing these relations to vary means giving a smooth function 
$$F : M \to \mathrm{Gr}_k(\mathbb{C} \oplus V \oplus V^{\otimes 2})$$
and considering the "bundle" (sheaf?) of algebras 
$$ A_p = T(V)/ \langle F(p)\rangle, \quad p \in M $$
over $M$.
However, I'm not sure if that completely captures what I want.  I might also insist that the projection of each $F(p)$ onto $V^{\otimes 2}$ has no kernel (which is not the case for the first example I described, but is the case for the second).
Question 3

Given the setup just described (or an appropriately modified version of your choosing), what are some conditions on $M$, $F$ such that the property "$A_p$ is a matrix algebra" is local on $M$?

For this question I am mainly interested in the cases when $M = \mathbb{R}$ or $M = \mathbb{C}$, although more general base spaces are of course interesting as well.
I have heard about something called the Azumaya locus which may be related to this, but I don't really know anything beyond the name.
I didn't realize this would be so long!  If you're still with me, thanks for reading.
 A: Your setup is very algebraic and I am not sure about the right answer in an algebraic geometric setup. However, in a more topological setting, a rigidity property was proved in
B. Blackadar, Shape theory for $C^\ast$-algebras. Math. Scand. 56 (1985), no. 2, 249–275.
There, it was shown that finite-dimensional matrix algebras (an many other interesting $C^\ast$-algebras) enjoy properties in the category of $C^\ast$-algebras which are analogous to properties of ANR's in the category of compact Hausdorff topological spaces. In particular, if the relations of a finite-dimensional matrix algebra $M_n \mathbb C$ (given by finitely many generators and finitely many relations) are satisfied up some sufficiently small $\varepsilon$ in the operator norm in any $C^*$-algebra $A$, then one can find a copy of $M_n \mathbb C \subset A$ nearby.
Formally, any almost-homomorphism $\pi \colon M_n \mathbb C \to A$ (i.e. $\|\pi(ab) - \pi(a)\pi(b)\| \leq \varepsilon \|a\|\|b\|, ...$ for a suitable $\varepsilon$) is close to an actual $*$-homomorphism.
A: While I don't know the answer to the questions as I don't quite understand them, let me offer some remarks. 
There's sort of a ''misunderstanding'' of what a deformation is. What you are discussing here is only i very special case of a formal deformation. In general a deformation should take place in a (dream) moduli space of the objects you're deforming. As such a ''global'' space is rarely exists, one is forced to study the problem locally and/or formally (meaning that the deformation is described with a formal power series ring). 
Let us look at the formal case first as this is usually the first step in a deformation problem, the goal being to construct the completion of the local ring of the moduli space. To every deformation problem there is a cohomology theory attached. The first thing that one has to do is determine what this theory is. When this is done one computes is the tangent space to the moduli space in the point (object) one is interested in (in your case a matrix). This tangent space is described by the first cohomology group in the cohomology theory (usually some $\mathrm{Ext}^1$-group). Then one tries to ''lift'' this deformation to higher order deformations in order to obtain something formal. This is done by ''killing'' obstructions at each level in the lifting. These obstructions live in a second cohomology group (usually some $\mathrm{Ext}^2$). When all obstructions are zero the deformation problem is said to be ''unobstructed'' and the ring describing the deformation is a formal power series ring. This case is very rare but happens in many deformation problems at specific points. 
(I want to point out that deformations are only defined modulo some equivalence relation and this is in fact a very important thing to remember.)
Ok, this formal ring (i.e., a ring that is a quotient of a formal power series ring) is now to be considered the completion of the local ring to the point in the moduli space. In your setup this corresponds to a deformation in one formal direction in the moduli space. However, you are implictly assuming that the deformation is unobstructed as you haven't factored out by any obstructions (i.e., there are no relations in the deformation ring). 
Alas, this is only a formal construction and not "useful" in geometry (at least in algebraic geometry; I suppose that in complex or analytic geometry the formal case would be ok, but I'm not really qualified to answer that). In any case, one needs an algebraization (think from formal power series to polynomial algebras). There is a deep theorem due to Micheal Artin saying that in many situation such an algebraization exists, but it is far from true in general and can be very hard to decide in specific cases. 
Let's say we have algebraizations around every point in ''moduli space''. One initial hope is to glue all these algebraizations to a global object. Unfortunately this is seldom possible in the category of schemes. A way out of this is to consider algebraic stacks but that's a whole other story. In any case, locally (formally) the moduli is described by the (completed) deformation rings. 
The deformation you're considering comes from the ''Gerstenhaber school'' which is, as I said, only a formal deformation in one direction with the assumption that the deformation problem is unobstructed. However, these kinds of deformations often appear as ''quantizations'' of Poisson algebras, Lie algebras, quantum groups etc. But in a strict sense they are not deformations. 
Ok, as for your problems, I don't quite understand how you're supposed to deform a non-commutative algebra with a commutative deformation ring. To me this seems to be an utterly impossible thing to do, at least if I understand your setup correctly. You could possibly make sense of this in some way but I don't know how. Therefore I would certainly say that the problem is rigid (or undefined even). 
If you were to deform specific matrices that is a very different thing, and certainly possible, at least if you forget the equivalences. However, and this is important, taking into account these equivalence effectively destroys the moduli space although locally it may well exist. In other words, it is not possible to glue the deformation rings in a sensible way without going to the stack language. 
As far as I can see, the Azumaya locus has no direct connection to deformation theory. It has to do with sheaves of algebras over a scheme such that locally it is a full matrix algebra. The Azumaya locus is the points on the schemes where this occurs. 
The other questions seem to be related to Cherednik algebras. See papers by Ian Gordon and collaborators. 
Edit: Oh, I forgot question 2, but I see that DamienC has already given a correct answer to that question. Not much more to say. Let me note however, that the only reasonable deformations in algebraic geometry are the flat ones, although in principle you could take more general morphisms. 
A: This isn't an exact answer to the question, but it might be of interest. The algebra of matrices might not have interesting deformations, but it does seem to have an interesting degeneration. More precisely, there is an algebra $A_t$ with $A_t \cong M_n(\mathbb C)$ when $t \not= 0$ such that $A_{t=0}$ is an interesting algebra. (See sections 1.1 and 2.3 of this paper by Allen Knutson and Paul Zinn-Justin.)
A: Deformation of relations
Answer to question 2 is the following: a deformation of an algebra $A_0$ parametrized by a pointed affine scheme $*\to X=Spec(B\to k)$ is the data of a $B$-algebra $A$ such that $A_0\cong A\otimes_B k$. 
Observe that the kind of deformations your are looking at in question 1 are those that are called "flat". 

Deforming structure constants of matrix algebras
In order to find the answer to question 1 (which is yes) I would suggest you to use Artin–Wedderburn theorem. 
EDIT 1: more precisely, over $\mathbb{C}$ any finite-dimensional (semi-)simple algebra is isomorphic to (a Cartesian product of) matrix algebras.
EDIT 2: Anyway, it seems that there is a more general phenomenon (see the fondational paper of Gerstenhaber, On the deformation of rings and algebras, Ann. of Math. 79 (1), (1964),
59–104): 
$$
\textrm{absolute rigidity}\Rightarrow \textrm{analytic rigidity}\Rightarrow \textrm{geometric rigidity}
$$
where absolute rigidity means that $HH^2(A)=0$, analytic rigidity means that there are no non-trivial formal deformations of $A$, and geometric rigidity means that the $GL(V)$-orbit of the point defined by $A=(V,c_{ij}^k)$ in the variety of structure constants on $V$ is open (this tells you in particular that sufficiently small deformations are trivial). You can conclude by using that 
$$
\textrm{semi-simplicity}\Rightarrow\textrm{absolute rigidity}
$$

Azumaya algebras
Finally, if I understand well your question 3, your guess seems correct: the right notion to look at is precisely the one of Azumaya algebra (if you are interested by the relation to Cherednick algebras mentionned in the answer of Daniel Larsson, I would suggest you to take a look at the last two or three chapters of this book by Pavel Etingof). 

Final remark
Let me also mention that there is a lot of work about deformation theory of quadratic algebras by sub-quadratic ones (see references given in this MO answer - EDIT: sorry, you already know this since you're the one who actually asked the question!)
