Considering the CONDSTORE/QRESYNC/caching code has been entirely 
rewritten for Horde_Imap_Client v2.0.1, this issue has likely been 
resolved.  Will mark as such and can be reopened if 2.0.1 doesn't fix.

This happens to me aswell,

I don't know if it's the same but I've got two spam/ham addresses to 
forward spam/ham to for retraining configured in imp (current 
horde-webmail-edition) and to move spam to "Spam" and ham to INBOX.

Everything works well, except that messages which have been moved 
reappear as duplicates after a couple of minutes (I guess after some 
refresh/cache purge/whatever), with the exact same message id and even 
the spam/ham mark on it.

And gone. Man this is annoying. I'll keep this open until I see this 
happening again and can get an IMAP log.

Aaand back again.

Seems to work again.

Still can't reproduce.  Only thing I can possibly think of is that 
this might be a duplicate of #11427.

But the message is not deleted. This is the JSON response:

{"response":true,"msgs":[{"charset":"UTF-8","message":"Die Nachricht 
\"We offer Straight forward h...\" wurde als Spam 
gemeldet.","flags":[],"type":"horde.message"},{"charset":"UTF-8","message":"Die Nachricht wurde 
gel\u00f6scht.","flags":[],"type":"horde.message"}],"tasks":{"imp:viewport":{"cacheid":"V968256253|H35918|9|1|D091212","data":[],"metadata":{"readonly":0,"thread":{"293610":"3","293609":"4","293607":"","293606":"3","293605":"4","293608":"","293590":"","293585":"","293566":"003","293562":"03","293542":"3","293538":"","293454":"","293030":"","292853":"3","292756":"4","292701":"","292671":"","292557":"","292396":"","292098":"","291960":"","291745":"","291714":"","291716":"3","291715":"4","292016":"003","292013":"002","292014":"002","292010":"03","293007":"01003","292707":"0103","292481":"013","291741":"02","291708":"02","291693":"3","291640":"","291567":"3","291319":"103","291312":"13","291234":"4","291189":"","291155":"","291139":"","291119":"","290870":"","290788":"","290835":"3","290759":"","290372":"","291235":"0003","291166":"003","291165":"03","291150":"3","290093":"","290000":"","289995":"","289848":"","289543":"","289519":"","289539":"","289516":"","289537":"","289535":"","28957
2":"","289570":"","289568":"","289499":"","289498":"","290195":"03","289492":"3","289491":"4","289490":"","289487":"","289486":"","289489":"","289477":"","289501":"0000000003","289496":"000000000103","289495":"00000000013","289494":"0000000002","289493":"0000000002","289485":"000000003","289484":"0000000013","289483":"000000002","289488":"00000000103","289482":"0000000013","289481":"000000002","289480":"00000003","289479":"00000002","289478":"00000002","289476":"0000003","289475":"000003","289474":"00003","289473":"0003","289472":"003","289471":"002","289470":"03","289469":"3","289468":"2","289467":"","289465":"","289466":"3","289464":"","282796":"3","280506":"4","279835":"3","279757":"","278676":"","277668":"","277949":"00000003"}},"rowlist":{"293610":1,"293609":2,"293607":3,"293606":4,"293605":5,"293608":6,"293590":7,"293585":8,"293566":9,"293562":10,"293542":11,"293538":12,"293454":13,"293030":14,"292853":15,"292756":16,"292701":17,"292671":18,"292557":19,"292396":20,"292098":21,"
291960":22,"291745":23,"291714":24,"291716":25,"291715":26,"292016":27,"292013":28,"292014":29,"292010":30,"293007":31,"292707":32,"292481":33,"291741":34,"291708":35,"291693":36,"291640":37,"291567":38,"291319":39,"291312":40,"291234":41,"291189":42,"291155":43,"291139":44,"291119":45,"290870":46,"290788":47,"290835":48,"290759":49,"290372":50,"291235":51,"291166":52,"291165":53,"291150":54,"290093":55,"290000":56,"289995":57,"289848":58,"289543":59,"289519":60,"289539":61,"289516":62,"289537":63,"289535":64,"289572":65,"289570":66,"289568":67,"289499":68,"289498":69,"290195":70,"289492":71,"289491":72,"289490":73,"289487":74,"289486":75,"289489":76,"289477":77,"289501":78,"289496":79,"289495":80,"289494":81,"289493":82,"289485":83,"289484":84,"289483":85,"289488":86,"289482":87,"289481":88,"289480":89,"289479":90,"289478":91,"289476":92,"289475":93,"289474":94,"289473":95,"289472":96,"289471":97,"289470":98,"289469":99,"289468":100,"289467":101,"289465":102,"289466":103,"289464":10
4,"282796":105,"280506":106,"279835":107,"279757":108,"278676":109,"277668":110,"277949":111},"totalrows":245,"view":"SU5CT1g","rowlist_reset":1},"imp:flag":[{"add":["$junk"],"uids":"{7}SU5CT1g293608"},{"remove":["$notjunk"],"uids":"{7}SU5CT1g293608"}],"imp:poll":{"SU5CT1g":7}}}

Everything looks good here.  Message is marked as spam, moved to spam 
mailbox, deleted from the current mailbox, and the mailbox is 
re-indexed:

C: 5 UID STORE 293536 (UNCHANGEDSINCE 35756) +FLAGS $junk
S: * 236 FETCH (FLAGS ($Junk) UID 293536 MODSEQ (35757))
S: 5 OK Completed
C: 6 UID STORE 293536 (UNCHANGEDSINCE 35757) -FLAGS $notjunk
S: 6 OK Completed
C: 7 UID COPY 293536 INBOX.Trash
S: 7 OK [COPYUID 984270706 293536 1245468] Completed
C: 8 UID STORE 293536 (UNCHANGEDSINCE 35757) +FLAGS \deleted
S: * 236 FETCH (FLAGS (\Deleted $Junk) UID 293536 MODSEQ (35758))
S: 8 OK Completed
C: 9 UID EXPUNGE 293536
S: * VANISHED 293536
S: 9 OK [HIGHESTMODSEQ 35759] Completed
[...]
C: 13 UID THREAD REFERENCES US-ASCII ALL
S: * THREAD (103113)(108842)(119429)(122132)(128290 127950)(135928 
135940)(142273)(142914)(166869)(170018)(171562)(173586)(173662)(173706)(175599)(175692)(175816)(177278 178049)(177358)(178661)(179694)(180119 181094 181118 181122)(181338)(184164)(184848)(186094)(186756)(187059 187076)(188416)(188466)(188642)(188907)(189008 189010)(192956)(190348)(190880)(191123)(194127)(194235)(195944)(196164)(196606)(202535)(205645)(206295)(206788 206993)(206818)(207164)(207229)(207254)(207313)(207439)(207671)(208041)(208282 208283 208285 208286 208299 (208300)(208303 208304 208306 208310 208324 208328 208367 208372))(208319)(212054)(213533)(213681)(213960)(213961)(215546)(216809)(222960)(226868 227085)(229490)(229856)(230020)(230415)(230503 230586)(230638)(231356)(233361)(234053)(239385)(239656)(244008)(247362)(247363)(254752)(255678)(255679)(256149 256152)((256829)(283596))(267570)(279758)(269016)(270336)(270337 270339)((271378)(273061 273135))(271696)(272281)(272841)(275128)(275148)(275289)(276929)(277052 279073 277064 279074 277159 277250 277598 277609 277949)(277668)(278676)(279757 279835)((280506)(282796))(289464 289466)(289465)(289467 (289468)(289469 289470 (289471)(289472 289473 289474 289475 289476 (289478)(289479)(289480 (289481 289482 289488)(289483 289484)(289485 (289493)(289494 289495 289496)(289501))))))(289477)(289489)(289486)(289487)(289490)((289491)(289492 290195))(289498)(289499)(289568)(289570)(289572)(289535)(289537)(289516)(289539)(289519)(289543)(289848)(289995)(290000)(290093 291150 291165 291166 291235)(290372)(290759 290835)(290788)(290870)(291119)(291139)(291155)(291189)((291234 291312 291319)(291567))(291640 291693 (291708)(291741 292481 292707 293007)(292010 
(292014)(292013)(292016)))((291715)(291716))(291714)(291745)(291960)(292098)(292396)(292557)(292671)(292701)((292756)(292853))(293030)(293454)(293534)(293535)
S: 13 OK Completed (235 msgs in 0.010 secs)

I see this in all views. Sometimes more often, sometimes rarely, 
messages reported as spam are not deleted, even though IMP is sending 
a notification that it did. Attached is an IMAP log from reporting a 
single message in traditional view.