As you say, four points (without their associated "$t$" values) are not enough to define a planar cubic Bezier curve.
In fact, 6 points are needed. But, on the other hand, the 6 points have to satisfy certain conditions, or else the required curve does not exist. In your case, you know that the curve exists, because it was used to generate the points in the first place.
The full story is given in this paper: J. Kozak, M. Krajnc, Geometric interpolation by planar cubic polynomial curves, Comput. Aided Geom. Des., 24 (2007), pp. 67-78. You can get a copy of the paper at the authors website.
Another approach (instead of the clever techniques suggested in the paper) is to use brute-force numerical methods. Start with 6 points $X_1, \ldots, X_6$ and 6 parameter values $t_1, \ldots, t_6$. We can assume that $t_1 = 0$ and $t_6 = 1$, but $t_2, t_3, t_4, t_5$ are unknown.We want to find control points $P_1, P_2, P_3, P_4$ for our curve. Obviously we can set $P_1 = X_1$ and $P_4 = X_6$, but $P_2$ and $P_3$ are unknown. We can (numerically) find values of $t_2, t_3, t_4, t_5$ and $P_2$ and $P_3$ that minimize the quantity
$$ \sum_{i=2}^{i=5}\Vert C(t_i) - X_i \Vert^2 $$
where $C(t)$ is the Bezier curve with control points $P_1, P_2, P_3, P_4$. This is a fairly nasty non-linear problem, but a good numerical algorithm will usually converge to the desired solution, given a decent starting point.
Another numerical approach: with the same notation we used above, solve the equations:
$$ C(t_i) = X_i \quad (i = 2,3,4,5)$$
Since the $X_i$ are 2D points, there are 8 equations here. We have 8 unknowns -- $t_2, t_3, t_4, t_5$ and the $x$ and $y$ coordinates of $P_2$ and $P_3$. The equations are non-linear, but a good numerical root-finding package should be able to handle them.
A much better approach is to get the Bezier curves from the CAD package. If the design guys won't give you the curves, you should charge them more money for your services, since they are making your life so much more difficult. Their choice -- curves or cash :-)
The article you cited is wrong (or, at best, misleading). In general, the offset of a Bezier curve can not be represented exactly as another Bezier curve (of any degree). But, on the other hand, there are many situations where you don't need an exact offset, you only need a decent approximation. In my view, the definitive works in this area are the following two papers:
Farouki and Neff: Analytic properties of plane offset curves, CAGD 7 (1990), 83-99
Farouki and Neff: Algebraic properties of plane offset curves, CAGD 7 (1990), 101-127
For a good comparison of available approximation techniques, look at this paper:
http://www.cs.technion.ac.il/~gershon/papers/offset-compare.pdf
Regarding special cases: Bezier curves that happen to be straight lines can obviously be offset exactly, as you observed. Also, so-called Pythagorean Hodograph curves have offsets that are rational Bezier curves, at least, but not polynomial ones. Ask again if you're interested in these.
The 90 degree idea is not very useful, even as an approximation guideline. As an example, consider the curve that has control points (0,0), (2,1), (0,1), (2,0). It satisfies the given conditions, but it's very difficult to offset accurately.
Best Answer
If you would like to minimize the "sharpness" of the cubic Bezier curve honoring two end points and two end tangent directions, there is something called "optimized geometric Hermite curve" (OGH curve) that might be interested to you. The OGH curve does not minimize the maximum curvature of the curve. Instead, it minimizes the overall "strain energy" of the curve, which is
$$\int_0^1 [f^"(t)]^2 \;\mathrm{dt}$$
You can refer to this paper link for details. For cubic OGH curve, you can find out the "optimal" magnitudes of the end derivatives analytically. The formula is listed in this paper as equation (4).