Sorry if this sounds a little clueless, but it sounds like the problem is because there's multiple Unicode standards (UTF-8, UTF-16, UTF-32). So it seems like if you just re-encode everything into one of these before committing to the storage layer, that you'd avoid this problem altogether, and you'd be able to do operations in the storage layer correctly too.