What are some good, fast persistent storage options for key->value data?
Short answer: Membase.
Long answer:
You basically have three options: a relational database, file storage, or something else.
Like you said, a relational database could definitely be overkill. That said, if this is part of an application that already has a MySQL or other database, I would go with that. Likewise, file storage can be handy sometimes (writing to a bunch of XML files, for example), but disk I/O can be slow.
Now in the other category, you have some great NoSQL options like CouchDB or Memcached.
If you aren't too worried about the persistence of your data, I'd recommend memcache. It's lightweight, easy to get running, and there is a Memcache PHP extension that makes using it easy. It is made for key-value storage like this.
The one drawback memcache has is that all your data is lost the second the memcache service stops. This is where Membase comes in. It is an open-source fork of memcache that is protocol-compatible, meaning it will work with all existing client libraries. However, it can persist your data and actually provide consistency and reliability, something memcache can't on its own.
NOTE: This answer is a relic of its time, as is the question itself. Please do not take it literally.
Just to suggest something different, redis (or redisdb-win32 if you're on a Windows servers)