So my knight got poisoned and I got him to Temple Gauche in Erliquin to be healed for a hefty 100 gold. He lost his poisoned status and his hp returned to 33, as it was before the poison. However, the MAX HP remains at 16. What the heck is wrong? The health is now 33/16. If I heal him with my cleric, it returns to 16/16. :(

EDIT: Lord Almighty, it seems a rest was all I needed or something. Resting at an inn did the trick for me, finally. Phew?

In Might and Magic 2 (and probably 1 as well), the game keeps two copies of your stats: the current value and the normal stat. When you rest, every stat is set to its normal value. (In MM2 at least, every non-HP stat gets reset at the end of the battle unless the character individually ran away.) The notable exception, of course, is maximum HP for poisoned characters, which is set to half its normal value.

Note that, in MM2 (don't know about MM1, since I have yet to play it), events that permanently change stats won't have any effect until the stat resets. Most notably is one event that gives your party lots of HP; you will need to rest to benefit from that HP (and in turn lose the effect of Max HP potions).

One more thing to note: I believe MM2 fixed the problem described in the OP. Your stats go back to their normal scores when a character is healed at the temple. Unfortunately, this makes it harder to take full advantage of Max HP potions.

One more thing: At leat in MM2 (don't know about 1), the HP loss from poison is not applied until you rest, so if possible, cure the poison before you rest.