Store raw data in cookies - good idea or a bad idea?

I want to store a list of recently viewed profiles in a cookie.
I have a site where people enter game character id (World of Warcraft) and can view the character's profile.
Character identity consists of name (unicode, up to 15 characters), server name (unicode, up to 25 characters), and zone (2 characters, latin-1).
I store up to 5 recently viewed characters in cookies, URL-encoding the values, since not all browsers are unicode-cookie friendly.

This makes this cookie up two 500 characters long.

Question: is this a reasonable approach? Here are few other solutions I would like you to evaluate.

1. Store characterId as it is defined in the database. Pros: small cookie size, Cons: a) character can be removed from the database (database is just a cache to speed up update), b) database can get re-indexed.
2. store name+server+zone hash, and look it up by hash in database. Cons: a) again, character can be removed from the database, Pros: reindexing resistant.
3. require a user to create an account and store it there. Cons: nobody likes creating accounts, and I rather not do this.

Am I splitting hairs and my present solution (store URL-encoded list in a cookie) is good enough?

EDIT: It is important to note that "recent characters" list is there just for convenience, if it gets cleared - it is not a problem at all (it's akin to a 'recent files' in some applications).

If you are not experiencing problems (or limitations) with your current solution, I would keep it as is. Be aware, by storing the entire character, and presenting that data, the data could be outdated.

I would store the ID's in a cookie and do some server side logic to return the available characters from the list of ID's. ID's which are not present in the database can be skipped from displaying and turning up in the list of ID's again.