There are two categories that have problematic identifiers. Would it be possible to rename them?
parsing — The name itself doesn't make it clear it's only about making parsers, and not parsing specific file formats. The description is clear about it, but apparently that's not enough: there are lots of miscategorized crates. I suggest parser-tooling as in "tools for making parsers", to stay clear from incorrect "parsing (…file formats)" interpretation.
game-engines — It's too specific. There are many utility libraries related to game development that are smaller than an "engine" (e.g. just sprite or animation libs, maze generators, multiplayer networking, dice rolls, chess moves, game-oriented collisions or math utils). I suggest game-dev which is the industry's catch-all term.
I suggest keeping the old name as an alias for backwards compatibility (so a "game-engines" crate would still appear in the "game-dev" category), but showing only the new name to user after the rename.
Would it be possible to only grandfather in the existing crates, while disallowing any new upload (even a new version) with it? More restrictive, but it would ensure anyone updating crates ensures it's in the appropriate category.
For the "parsing" category it would be nice to have a warning, so that authors can review it and clarify categorization.
But for other categories and invalid categories in general, I don't see the need to be strict about them. The aliases may need to stay indefinitely to support already published crates. I haven't checked if Cargo has checking of categories yet, but there are crates published with invalid categories. For https://lib.rs it isn't a big deal: I just move invalid category names to keywords.
This sounds like the best approach to me. I think the API is also capable of issuing warnings, so perhaps it could warn if you publish using a legacy name.