About alankila's patch: I don't like that it keeps a reference to the spawned thread (its runnable) and uses it synchronously without synchronizations.
About Andrea's patch: I think using blockingQueue is better performing than synchronized LinkedHashMap.
About Pertl's patch: using LinkedBlockingQueue will grow without upper limit and may lead memory problems. Using Thread.interrupt() may interrupt the thread in the middle of its job (page storing). This may or may not lead to problems later, I'm not sure. I don't see functional problems with the AtomicBoolean flag.
Some notes on the current impl: It adds entries to the queue up to its capacity. These entries will be saved asynchronously. If there is a heavy load and the queue is full then the entries are added synchronously as they are when AsynchronousDataStore is not in use. This way the user application decides how big queue to use depending on the load they expect and the RAM they can affort.