Adding the assumption that you're asking about Banach $*$-algebras with isometric involution, your question Why is $\ell^1(\mathbb{Z})$ not a $C^{*}$-algebra? has the example $\ell^1(\mathbb Z)$.
Another is the algebra of bounded analytic functions on the unit disk with sup norm and involution $f^{*}(z)=\overline{f(\overline z)}$.
You mention matrices, and implicitly you seem to be assuming that $M_n$ is given the operator norm from acting as operators on $\mathbb C^n$ with the standard inner product, or equivalently $\|a\|=\sqrt{\text{the spectral radius of }a^*a}$, where $a^*$ is the conjugate transpose of $a$. But if you give $M_n$ another submultiplicative norm that makes the conjugate transpose norm-preserving, then you will not have a $C^*$-algebra. One example is the Frobenius norm, a.k.a. the Hilbert–Schmidt norm, $\|a\|=\sqrt{\mathrm{Trace}(a^*a)}$.
You say that the upper-triangular matrices satisfy the $C^*$-identity, but it is not clear what that means when they don't have an involution. If you are asking about $*$-algebras, then subalgebras of $*$-algebras that are not closed under the involution are out of the picture.
The first example above, $\ell^1(\mathbb Z)$, fits into a bigger picture of considering the Banach $*$-algebra $L^1(G)$ of a locally compact Hausdorff group $G$ with Haar measure, which sometimes arises in the study of group representations.
One thing that makes $\ell^1(\mathbb Z)$ more interesting than $M_n$ with the Frobenius norm as an example is that $\ell^1(\mathbb Z)$ is not even isomorphic as an algebra to any $C^*$-algebra.
Here's an answer for your question 1. which has two parts:
a) [An example of a] Banach *-algebra that is not a C*-algebra for which there exists a positive linear functional (it takes $x^*x$ to numbers $ \geq 0$) that is not norm continuous.
As far as I know all “explicit” counterexamples are based on Dixon's construction, and they are quite complicated. In 1982 H.G. Dales proved:
There is a Banach *-algebra with a norm-discontinuous trace, i.e. a positive linear functional $\tau$ such that $\tau(ab) = \tau(ba)$ for all $a,b \in A$.
See Example 4 of H.G. Dales, The Continuity of Traces, in Radical Banach algebras and automatic continuity, Lecture Notes in Mathematics, 975, Springer Verlag, (1982), 451–458. To understand the construction in that article you will need a copy of P.G. Dixon's paper, Non-separable Banach algebras whose squares are pathological, J. Functional Analysis, 26 (1977), 190–200.
Remark. That this example must be rather complicated is not really surprising since it is impossible to “write down” a discontinuous linear map, and it is obviously even harder to write down a discontinuous linear map satisfying further algebraic constraints: a discontinuous linear map necessarily involves the axiom of choice in a strong form, e.g. existence of algebraic bases, since it is consistent with ZF+DC that all linear maps between Banach spaces are continuous. In fact, the (non)existence of discontinuous homomorphisms on $A = C(K)$ is independent of the usual axioms of set theory, see also Andres Caicedo's answer here.
b) Apparently if a Banach *-algebra so much as even has a bounded approximate identity, then all positive linear functionals are continuous. Does anybody have a proof of this?
Yes. More generally, Theorem 5.5.10 on page 698 of H.G. Dales, Banach Algebras and Automatic Continuity states the automatic continuity of a positive linear functional on a Banach algebra with a not necessarily continuous involution and a bounded approximate left identity. Here's an outline of the argument in the simpler case of an isometric involution:
Suppose that $A$ is a Banach *-algebra with a bounded approximate identity.
Arguably the most important single result in automatic continuity theory is the Cohen-Hewitt factorization theorem. In one of its most basic forms it can be phrased as follows:
Let $A$ be a Banach algebra with a bounded approximate left identity $(u_i)_{i \in I}$ and let $M$ be a left Banach $A$-module. For $m \in M$ the following are equivalent:
There are $a \in A$ and $n \in M$ such that $m = an$
$\lim_{i} \lVert u_i m - m\rVert = 0$.
A short proof (very close to Hewitt's argument) can be found in Cigler–Losert–Michor, Banach modules and functors on categories of Banach spaces, Theorem III.1.15 on page 108 (they are assuming that the approximate identity is in the unit ball of $A$ but the proof is easy to adapt to the more general statement given here).
Over time the factorization theorem has been sharpened in many ways and entire books were written about it: R.S. Doran, J. Wichmann Approximate Identities and Factorization in Banach Modules. See also Chapter 2 of Dales's comprehensive Banach Algebras and Automatic Continuity.
Some further remarks:
If all $m \in M$ satisfy the conditions of the factorization theorem then $M$ is called an essential $A$-module.
Since the definition of an approximate identity is property 2. for all $a \in A$ when $A$ is considered as a left $A$-module, one immediate consequence of the theorem is that every $a \in A$ factors as $a = bc$. For $A = L^1(G)$ this is Cohen's original form of the factorization theorem.
An easy lemma on essential modules $M$ is that the space $c_0(M) = c_0(\mathbb{N},M)$ of null sequences in $M$ with the norm $\lVert (m_n)_{n \in \mathbb{N}}\rVert_{c_0(M)} = \sup_{n \in \mathbb{N}} \lVert m_n \rVert_M$ is an essential module (check that property 2. is satisfied for $c_0(M)$). This implies that every null sequence $m_n \to 0$ in $M$ can be factored as $m_n = a x_n$ with $a \in A$ and $x_n \to 0$ in $M$.
[Incidentally, this can be used to show that a right $A$-linear map $\varphi\colon A \to N$ into a right Banach $A$-module is automatically continuous by observing that $a_n \to 0$ implies $a_n = ab_n$ with $b_n \to 0$ so that $\varphi(a_n) = \varphi(a)b_n \to 0$.]
The proof of continuity of positive linear functionals on a Banach *-algebra with a bounded approximate identity is now relatively easy:
Recall the Cauchy-Schwarz inequality for positive linear functionals $f$:
$$
\lvert f(ab a^\ast)\rvert \leq f(aa^\ast) \cdot \sqrt{\rho(bb^\ast)},
$$
for all $a, b \in A$, where $\rho(x) = \lim_{n\to\infty} \lVert x^n\rVert^{1/n}$ is the spectral radius of $x \in A$.
It follows from this that $x \mapsto f(a x a^\ast)$ is continuous for all $a \in A$ and thus $x \mapsto f(ax b^\ast)$ is continuous for all $a,b \in A$.
Now let $x_n \to 0$. We want to show that $f(x_n) \to 0$. By the factorization theorem (remark 3. above), we can write $x_n = a c_n$ with $c_n \to 0$. Now $c_n^\ast \to 0$, so we can write $c_n^{\ast} = b d_n$ with $d_n \to 0$. Thus, $x_n = a d_n^\ast b^\ast$ with $d_n \to 0$, so $f(x_n) = f(a d_n^\ast b^\ast) \to 0$, as desired.
Best Answer
For an example of non-unital Banach algebra, define $a\cdot b = 0$ for any $a,b\in\mathbb C^n$.
To prove this statement, note that the closed unital ball of any finite dimensional Banach space is compact, therefore by the third property $\|e_{\alpha}\|\le 1$, there exists a convergent subnet $e_{\alpha_\beta}\rightarrow e$. And by the first two properties we can show that $e$ is an identity of the Banach algebra.