Is there anyway that I could add "persistent" metadata to entities so that the values aren't on reload/restart?
If you can convert that metadata into a string you can store strings on entities. See https://hub.spigotmc.org/javadocs/bukkit/org/bukkit/entity/Entity.html#getScoreboardTags().
MetaData is stored in String form. They're all just Strings. Loop all MetaData used, which I believe is max 16 anyways, and then save it?
Well I mean.. Minecraft does this with NBT tags, but I highly doubt you want to do it that way. - I tried, succeed even, but will not recommend. Store the MetaData - or whatever you need to store - on either a file or database, depending on the situation?
Adding it to the entity NBT data is the most reliable way to do this, as it will be automatically saved (assuming you use a tag known to the server).
Scoreboard tags are already saved to NBT, but it relies on you to format the Strings accordingly so you have to make sure it's in a format that is unique to your plugin.