The para-elementals are the inhabitants of the para-elemental planes,
Ice, Ooze, Magma, and Smoke, that lie between the major planes of
Earth, Air, Fire, and Water.
Para-elementals are summoned as normal elementals are,
except that there is a chance of not getting the summoned elemental but one from either of the major elemental planes adjoining it.
This chance is 100% minus 5% per level of the summoner.

Conjured para-elementals fall into 3 hit-dice-strength categories like
their major plane brethren:
those of 16 HD are conjured by spell;
those of 12 HD are conjured by summoning device;
and those of 8 HD strength are conjured by means of a staff.

Para-elementals are impervious to attacks from weapons of less than +1 enchantment
or by creatures without magical ability of 4 hit dice or less.
As with ordinary elementals, control over the para-elementals must be
maintained at all times, otherwise it will turn on its summoner. The
material components needed for summoning the para-elementals
(aside from a large amount of the <para->element) are as follows:
a lens of clear crystal or glass is used to summon ice elementals;
a damp cloth is used for ooze;
volcanic glass is used for magma;
and dry ash is used for smoke.
<a note can made at the individual entries>
<color>

<in UA, 21-24 HD elementals are mentioned. full details for these should be provided>
<MM.99: note the reference to "with magical power">

<On page 141 of the MM2, in the Very rare section of Level VII, there are 4 listed para-elementals. I've used the 4 on this page. The 'para-elementals' are most likely quasi-elementals, which shoul be detailed in Dragon magazine>
 

    Para-Elementals: Para-elemental creatures rarely stray from
their native planes; for this reason not many are known and identified
by Prime Material travellers.

    In temperament, para-elementals are generally wary, unfriendly,
and cautious toward others. This is not surprising as their
native planes are often turned into combat zones by competing
groups of elemental powers, and the para-elementals are not
included in the councils of the major elemental planes. This tends
to make these beings resentful at best and bad-spirited at worst.
Even so, large numbers of para-elemental creatures have information
about bordering planes because of the continual traffic
across their planes. They may share this information for a price.

    Para-elementals tend to be gruff and non-committal guides.
They can be bribed into service in the same manner as elementals
of the major planes, but items specifically appealing
to them (such as smoke essence or an ice-carving) ) entice them to
double their duration of service, These enticements have a 50%
chance of encouraging them to FIGHT with the party.

Source = Manual of the Planes