Changes have been made in Git (master):

commit b2632a1de65f76124522384a86f179beb8eef857
Author: Michael J Rubinsky <mrubinsk@horde.org>
Date:   Sun Aug 5 17:10:26 2012 -0400

     Fix synckey comparison. Must compare to a string.

     Possibly fixes Bug: 11315

  .../lib/Horde/ActiveSync/Request/Sync.php          |    6 +++---
  1 files changed, 3 insertions(+), 3 deletions(-)

http://git.horde.org/horde-git/-/commit/b2632a1de65f76124522384a86f179beb8eef857

It doesn't need to be named "Deleted Items', but you *must* be moving 
deleted items to the trash folder, not just marking them as deleted. 
I.e., the 'use_trash' preference must be set.
No. This is a bug in the WP7.5 client. We are not going to hack our 
code to work around MS's bug.

So in order to make WP7 and ActiveSync work I have to add line like 
this to prefs.local.php:
$_prefs['trash_folder']['value'] => 'Deleted Items'

Would it be possible to use one trash_folder setting for ActiveSync 
and another trash_folder setting for normal webmail users?

Sorry, I might not have been clear.  You already have a "Trash" folder 
in your folder hierarchy, but you do not have it flagged as what 
Exchange considers the "Deleted Items Folder". You need to tell IMP 
which of your folders is the Trash folder. This is done in the 
preferences for IMP.

I created a folder "Deleted Items" but ActiveSync still gives the same 
error: 8004010F

Link to bug mentioned in previous comment:

http://social.msdn.microsoft.com/Forums/en/os_exchangeprotocols/thread/86e10e2d-bc4d-43dc-b6b7-f02630ff052b

aaaaaand, after further searching, I believe *your* problem is that 
you do not have a "Deleted" items folder.

It seems that there was code introduced in Windows Phone 7.5 that 
inadvertently caused FOLDERSYNC to break when there is no Deleted 
items folder sent from the server. This is a bug in the client code 
and the suggested workaround from Microsoft is to enable the Deleted 
folder.

This is a user setting in IMP.  If you can verify that this is the 
issue, I'll add a note in the wiki, but there is nothing we can do 
server side to work around this.

Additionally, there are multiple postings in various (non-horde) 
forums about this error code and WinMo 7 devices.

A microsoft forum suggests changing the Locale setting on the phone, 
then setting it back to the original Locale, rebooting and re-pairing 
the sync partnership.

E.g., 
http://answers.microsoft.com/en-us/winphone/forum/wp7-sync/email-problems-with-htc-hd7-windows-phone-error/feb2d9d3-dd7d-4be3-87c5-5b2b99c3cdea

I cannot reproduce this error on any of my test devices, including a 
WinMo6.5 device, using a similar folder structure.

Is this the *entire* log? Also, are there any other errors reported in 
the horde/server log? If you can get a wiretrace of the conversation 
that might be useful as well.

I tried to patch and it did not seem to fix the problem. I still get 
the error 8004010F.

Actually, the folder names don't seem to be a problem from my testing.

However, there was an issue with initializing the sync object in 
certain code paths - one of which only a WinMo phone would follow.

See if the following fixes your issue:

http://lists.horde.org/archives/commits/2012-August/015779.html

Yep, well aware of this tool. Thanks.

Works fine here on all my test devices though I don't have a WP7 
device to test.

The log also looks fine. The server is sending exactly what it should 
be, but it looks like the device does not like something in it. My 
guess is that it's something to do with the sub folder structure.

There is also Remote Connectivity Analyzer for ActiveSync at:
https://www.testexchangeconnectivity.com/

ActiveSync always fails with Error Code: 8004010F

Attached ActiveSync synclog.

Tested with: Nokia Lumia 900 (Windows Phone 7.5)
Tried to sync: Email, Contacts, Calendar, Tasks