I had a similar issue with a macro to delete all items in my Trash folder. The solution was to loop in reverse from the count of items to 1. Using that approach the macro worked the first time. I hope this will work for you.

RetiredCHe