I have the same problem and I think I know what the issue is preventing it from being solved. I noticed that manfredall has marked his question as solved (calling it a OS X bug), but I believe I know why creating a new folder does not fully fix the problem and I need some help to implement the fix correctly.
When I created a new lsd directory and allowed the system to rebuild the com.apple.lsdschemes.plist file after a reboot, the "Could not store lsd-identifiers file" messages continued. Then, I looked at the same directory and file on a recent, Time Machine backup of this El Capitan (Mac OS X 10.11.1) system and I noticed both the directory and the file had extended () file permission attributes. These extended attributes are not automatically assigned when a new lsd directory is created and must be written to the com.apple.lsdschemes.plist file's attributes using the xattr command.
Here is the list of the extended attributes attached to the file from the backup of this El Capitan system (immediately after updating from Yosemite):
MacBook-Air:lsd user$ ls -l@ *
-rw-r--r--@ 2 root wheel 42 Oct 29 12:01 com.apple.lsdschemes.plist
com.apple.finder.copy.source.checksum#N 4
com.apple.metadata:_kTimeMachineNewestSnapshot 50
com.apple.metadata:_kTimeMachineOldestSnapshot 50
I strongly believe that if we assign the same extended attributes to the com.apple.lsdschemes.plist file inside the new lsd directory that we created, we will at least partially resolve this issue by restoring the LaunchServices process' ability to write to this file.
I know I need to use the xattr command, but I am not comfortable enough with my rusty UNIX skills to create the proper command. Can anyone help? Here is my first attempt at structuring the necessary commands:
xattr -w com.apple.finder.copy.source.checksum#N 4 com.apple.lsdschemes.plist
xattr -w com.apple.metadata:_kTimeMachineNewestSnapshot 50com.apple.lsdschemes.plist
xattr -w com.apple.metadata:_kTimeMachineOldestSnapshot 50com.apple.lsdschemes.plist
Do these look correct?
FWIW - Background (of how I got into trouble): Yesterday, during a Time Machine backup of a MacBook Air, I noticed the backupd process appeared to have stop/slowed approximately two-thirds of the way through the backup. When I looked at the Console log, I saw that various Spotlight processes were in a major "battle" with LaunchServices attempting to resolve a problem with the LaunchServices database. At this point, I decided to rebuild that database using the commonly used (since at least 2003) command:
/System/Library/Frameworks/CoreServices.framework/Frameworks/LaunchServices.framework/Support/lsregister -kill -r -domain local -domain system -domain user
I immediately realized that not only did this command not fix the problem, I started seeing a large number of Console messages that suggested I had made the problem worse.
10/29/15 11:35:42.685 AM lsd[253]: LaunchServices: Could not store lsd-identifiers file at /private/var/db/lsd/com.apple.lsdschemes.plist
Next, I decided to rebuild the LaunchServices database using the El Capitan (3.1.1) version of Onyx. That created the same problem and I had to manually recreate the lsd directory again.
Obviously, the method of rebuilding the LaunchService database has changed in El Capitan (Mac OS X 10.11.1) and has not been properly revised in Onyx 3.1.1 to be fully compatible and compliant. Thus, I would strongly recommend against using Onyx 3.1.1 to rebuild any OS X files until these types of issues have been fully flushed out.