Mods like Chat Patches add a chat history functionality that persists chat history through multiple worlds and game sessions. Unfortunately, the Chat Heads are lost on the chat history messages when exiting/restarting Minecraft. Not sure if this would be possible, but it would be really nice if somehow Chat Heads could still be shown/re-added to chat history messages.

Edit: Mod Patches -> Chat Patches

Yesn't, this is only partially doable and it looks like it'd require some hackwork.

It's possible to patch the part where Chat Patches adds the messages, adding heads using a heuristic at least, but it'll mismatch some heads and there's no easy way to store and restore the exact heads that were used for each message.
This is partial to issue #53 of us not caching heads, so we can only get them from players actively playing on the server, so some heads would be missing from the history either way.

There's a nice theoretical "fix" of rewriting Chat Heads to encode heads pixel by pixel as text by using a special font like Ryhon0 is doing for server-side heads in #69.
Because if the heads were just text, Chat Patches and co would just store/restore them like any other text, no hacky compatibility code needed.
(This would also fix issue #68 of not being able to place the heads in the middle of text.)
That said, I'm pretty sure this would cause new compatibility issues as well when the server is requiring its own special font, so it may not be the solution - the grass is always greener.

So right now, I'm not sure what to do about this, need to think some more about it.

Right, that all makes sense. Wish I could help on the technical side, but I'm afraid I don't have those skills. Hope you find a good solution one day! Really appreciate your work on this great mod.