Ordering a list of lists subject to constraints
This problem is an instance of the list coloring problem.  The list coloring problem is a variant of the graph color problem, where additionally have constraints that provide for each vertex a list of allowable colors that can be used for that vertex.

Here's the relationship.  Let $V$ denote the set of distinct values that appear in any row.  In Example 1, $V=\{A,B,C,D,E\}$; in Example 2, $V=\{A,B,C,D\}$.  Form an undirected graph $G$ where $V$ is the vertex set (so each value is a vertex).  Add an edge $(u,v)$ between two values if there is some row where those two vertices appear together.

Now suppose we want to arrange these in a matrix with $c$ columns (i.e., $c$ is the length of the longest row).  We'll imagine having $c$ colors, numbered from $1$ to $c$, where color $i$ corresponds to the $i$th column.  If the value $v$ is colored $i$, we take this to mean that every appearance of value $v$ should appear in column $i$.

Now from each row that is less than $c$ values long, we obtain some constraints.  In particular, if we have a row that is $\ell$ values long, then each value in that row needs to be colored with a color in the set $\{1,2,\dots,\ell\}$ (to ensure the lower-triangular requirement).  These are the lists that make this a list coloring problem.

Now any solution to the list coloring problem yields a solution to your problem: the colors tell you what column to put each value into, which tells you how to permute each of your rows to form a valid solution.  Therefore, you can use any algorithm for the list coloring problem to solve your problem.