diff --git a/tests/Sync/Sync/EmailTest.php b/tests/Sync/Sync/EmailTest.php
index c61326d..b62d6c6 100644
--- a/tests/Sync/Sync/EmailTest.php
+++ b/tests/Sync/Sync/EmailTest.php
@@ -1,326 +1,375 @@
 <?php
 
 namespace Tests\Sync\Sync;
 
 class EmailTest extends \Tests\SyncTestCase
 {
     /**
      * Test Sync command
      */
     public function testSync()
     {
         $this->emptyTestFolder('INBOX', 'mail');
         $this->registerDevice();
 
         // Test invalid collection identifier
         $request = <<<EOF
             <?xml version="1.0" encoding="utf-8"?>
             <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
             <Sync xmlns="uri:AirSync">
                 <Collections>
                     <Collection>
                         <SyncKey>0</SyncKey>
                         <CollectionId>1111111111</CollectionId>
                     </Collection>
                 </Collections>
             </Sync>
             EOF;
 
         $response = $this->request($request, 'Sync');
 
         $this->assertEquals(200, $response->getStatusCode());
 
         $dom = $this->fromWbxml($response->getBody());
         $xpath = $this->xpath($dom);
 
         $this->assertSame('12', $xpath->query("//ns:Sync/ns:Status")->item(0)->nodeValue);
 
         // Test INBOX
         $folderId = '38b950ebd62cd9a66929c89615d0fc04';
         $syncKey = 0;
         $request = <<<EOF
             <?xml version="1.0" encoding="utf-8"?>
             <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
             <Sync xmlns="uri:AirSync">
                 <Collections>
                     <Collection>
                         <SyncKey>{$syncKey}</SyncKey>
                         <CollectionId>{$folderId}</CollectionId>
                     </Collection>
                 </Collections>
             </Sync>
             EOF;
 
         $response = $this->request($request, 'Sync');
 
         $this->assertEquals(200, $response->getStatusCode());
 
         $dom = $this->fromWbxml($response->getBody());
         $xpath = $this->xpath($dom);
 
         $this->assertSame('1', $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:Status")->item(0)->nodeValue);
         $this->assertSame(strval(++$syncKey), $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:SyncKey")->item(0)->nodeValue);
         $this->assertSame('Email', $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:Class")->item(0)->nodeValue);
         $this->assertSame($folderId, $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:CollectionId")->item(0)->nodeValue);
 
         // Test listing mail in INBOX, use WindowSize=1
         // Append two mail messages
         $this->appendMail('INBOX', 'mail.sync1');
         $this->appendMail('INBOX', 'mail.sync2');
 
         $request = <<<EOF
             <?xml version="1.0" encoding="utf-8"?>
             <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
             <Sync xmlns="uri:AirSync" xmlns:AirSyncBase="uri:AirSyncBase">
                 <Collections>
                     <Collection>
                         <SyncKey>{$syncKey}</SyncKey>
                         <CollectionId>{$folderId}</CollectionId>
                         <DeletesAsMoves>1</DeletesAsMoves>
                         <GetChanges>1</GetChanges>
                         <WindowSize>1</WindowSize>
                         <Options>
                             <FilterType>0</FilterType>
                             <Conflict>1</Conflict>
                             <BodyPreference xmlns="uri:AirSyncBase">
                                 <Type>2</Type>
                                 <TruncationSize>51200</TruncationSize>
                                 <AllOrNone>0</AllOrNone>
                             </BodyPreference>
                         </Options>
                     </Collection>
                 </Collections>
             </Sync>
             EOF;
 
         $response = $this->request($request, 'Sync');
 
         $this->assertEquals(200, $response->getStatusCode());
 
         $dom = $this->fromWbxml($response->getBody());
         $xpath = $this->xpath($dom);
 
         $root = "//ns:Sync/ns:Collections/ns:Collection";
         $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
         $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
         $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
         $this->assertSame(1, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
 
         // Note: We assume messages are in IMAP default order, it may change in future
         $root .= "/ns:Commands/ns:Add";
         $this->assertStringMatchesFormat("{$folderId}::%d", $xpath->query("{$root}/ns:ServerId")->item(0)->nodeValue);
         $this->assertSame('test sync', $xpath->query("{$root}/ns:ApplicationData/Email:Subject")->item(0)->nodeValue);
 
         // List the rest of the mail
         $request = <<<EOF
             <?xml version="1.0" encoding="utf-8"?>
             <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
             <Sync xmlns="uri:AirSync" xmlns:AirSyncBase="uri:AirSyncBase">
                 <Collections>
                     <Collection>
                         <SyncKey>{$syncKey}</SyncKey>
                         <CollectionId>{$folderId}</CollectionId>
                         <DeletesAsMoves>1</DeletesAsMoves>
                         <GetChanges>1</GetChanges>
                         <Options>
                             <FilterType>0</FilterType>
                             <Conflict>1</Conflict>
                             <BodyPreference xmlns="uri:AirSyncBase">
                                 <Type>2</Type>
                                 <TruncationSize>51200</TruncationSize>
                                 <AllOrNone>0</AllOrNone>
                             </BodyPreference>
                         </Options>
                     </Collection>
                 </Collections>
             </Sync>
             EOF;
 
         $response = $this->request($request, 'Sync');
 
         $this->assertEquals(200, $response->getStatusCode());
 
         $dom = $this->fromWbxml($response->getBody());
         $xpath = $this->xpath($dom);
 
         $root = "//ns:Sync/ns:Collections/ns:Collection";
         $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
         $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
         $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
         $this->assertSame(1, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
 
         // Note: We assume messages are in IMAP default order, it may change in future
         $root .= "/ns:Commands/ns:Add";
         $this->assertStringMatchesFormat("{$folderId}::%d", $xpath->query("{$root}/ns:ServerId")->item(0)->nodeValue);
         $this->assertSame('sync test with attachment', $xpath->query("{$root}/ns:ApplicationData/Email:Subject")->item(0)->nodeValue);
 
         return $syncKey;
     }
 
     /**
      * Test empty sync response
      *
      * @depends testSync
      */
     public function testEmptySync($syncKey)
     {
         $folderId = '38b950ebd62cd9a66929c89615d0fc04';
         $request = <<<EOF
             <?xml version="1.0" encoding="utf-8"?>
             <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
             <Sync xmlns="uri:AirSync" xmlns:AirSyncBase="uri:AirSyncBase">
                 <Collections>
                     <Collection>
                         <SyncKey>{$syncKey}</SyncKey>
                         <CollectionId>{$folderId}</CollectionId>
                         <DeletesAsMoves>1</DeletesAsMoves>
                         <GetChanges>1</GetChanges>
                         <Options>
                             <FilterType>0</FilterType>
                             <Conflict>1</Conflict>
                             <BodyPreference xmlns="uri:AirSyncBase">
                                 <Type>2</Type>
                                 <TruncationSize>51200</TruncationSize>
                                 <AllOrNone>0</AllOrNone>
                             </BodyPreference>
                         </Options>
                     </Collection>
                 </Collections>
             </Sync>
             EOF;
 
         $response = $this->request($request, 'Sync');
 
         $this->assertEquals(200, $response->getStatusCode());
         // We expect an empty response without a change
         $this->assertEquals(0, $response->getBody()->getSize());
 
         return $syncKey;
     }
 
     /**
      * Test flag change
      *
      * @depends testEmptySync
      */
     public function testFlagChange($syncKey)
     {
         $this->assertTrue($this->markMailAsRead('INBOX', '*'));
 
         $folderId = '38b950ebd62cd9a66929c89615d0fc04';
         $request = <<<EOF
             <?xml version="1.0" encoding="utf-8"?>
             <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
             <Sync xmlns="uri:AirSync" xmlns:AirSyncBase="uri:AirSyncBase">
                 <Collections>
                     <Collection>
                         <SyncKey>{$syncKey}</SyncKey>
                         <CollectionId>{$folderId}</CollectionId>
                         <DeletesAsMoves>1</DeletesAsMoves>
                         <GetChanges>1</GetChanges>
                         <Options>
                             <FilterType>0</FilterType>
                             <Conflict>1</Conflict>
                             <BodyPreference xmlns="uri:AirSyncBase">
                                 <Type>2</Type>
                                 <TruncationSize>51200</TruncationSize>
                                 <AllOrNone>0</AllOrNone>
                             </BodyPreference>
                         </Options>
                     </Collection>
                 </Collections>
             </Sync>
             EOF;
 
         $response = $this->request($request, 'Sync');
 
         $this->assertEquals(200, $response->getStatusCode());
         $dom = $this->fromWbxml($response->getBody());
         $xpath = $this->xpath($dom);
         print($dom->saveXML());
 
         $root = "//ns:Sync/ns:Collections/ns:Collection";
         $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
         $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
         $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
         $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
         $this->assertSame(2, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
 
         return $syncKey;
     }
 
     /**
      * Retry flag change
      * Resending the same syncKey should result in the same changes.
      * FIXME: This doesn't currently work because we update the modseq information,
      * so on the next check syncroton thinks everything is up to date.
      *
      * @expectedException PHPUnit_Framework_ExpectationFailedException
      * @depends testFlagChange
      */
     public function testRetryFlagChange($syncKey)
     {
         $this->markTestIncomplete();
         $syncKey--;
         $folderId = '38b950ebd62cd9a66929c89615d0fc04';
         $request = <<<EOF
             <?xml version="1.0" encoding="utf-8"?>
             <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
             <Sync xmlns="uri:AirSync" xmlns:AirSyncBase="uri:AirSyncBase">
                 <Collections>
                     <Collection>
                         <SyncKey>{$syncKey}</SyncKey>
                         <CollectionId>{$folderId}</CollectionId>
                         <DeletesAsMoves>1</DeletesAsMoves>
                         <GetChanges>1</GetChanges>
                         <Options>
                             <FilterType>0</FilterType>
                             <Conflict>1</Conflict>
                             <BodyPreference xmlns="uri:AirSyncBase">
                                 <Type>2</Type>
                                 <TruncationSize>51200</TruncationSize>
                                 <AllOrNone>0</AllOrNone>
                             </BodyPreference>
                         </Options>
                     </Collection>
                 </Collections>
             </Sync>
             EOF;
 
         $response = $this->request($request, 'Sync');
 
         $this->assertEquals(200, $response->getStatusCode());
         $dom = $this->fromWbxml($response->getBody());
         $xpath = $this->xpath($dom);
         print($dom->saveXML());
 
         $root = "//ns:Sync/ns:Collections/ns:Collection";
         $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
         $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
         $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
         $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
         $this->assertSame(2, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
 
         return $syncKey;
     }
 
     /**
      * Test updating message properties from client
      *
      * @depends testSync
      */
     public function testChangeFromClient($syncKey)
     {
         $this->markTestIncomplete();
     }
 
     /**
      * Test deleting messages from client
      *
      * @depends testChangeFromClient
      */
     public function testDeleteFromClient($syncKey)
     {
         $this->markTestIncomplete();
     }
+
+
+    /**
+    * Test a sync key that doesn't exist yet.
+    * @depends testFlagChange
+    */
+    public function testInvalidSyncKey($syncKey)
+    {
+        $syncKey++;
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $request = <<<EOF
+            <?xml version="1.0" encoding="utf-8"?>
+            <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
+            <Sync xmlns="uri:AirSync" xmlns:AirSyncBase="uri:AirSyncBase">
+                <Collections>
+                    <Collection>
+                        <SyncKey>{$syncKey}</SyncKey>
+                        <CollectionId>{$folderId}</CollectionId>
+                        <DeletesAsMoves>1</DeletesAsMoves>
+                        <GetChanges>1</GetChanges>
+                        <Options>
+                            <FilterType>0</FilterType>
+                            <Conflict>1</Conflict>
+                            <BodyPreference xmlns="uri:AirSyncBase">
+                                <Type>2</Type>
+                                <TruncationSize>51200</TruncationSize>
+                                <AllOrNone>0</AllOrNone>
+                            </BodyPreference>
+                        </Options>
+                    </Collection>
+                </Collections>
+            </Sync>
+            EOF;
+
+        $response = $this->request($request, 'Sync');
+
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+        print($dom->saveXML());
+
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('3', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame('0', $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+
+        //We have to start over after this. The sync state was removed.
+        return 0;
+    }
+
 }