OK, so I have found a fix for this and will post here if someone else ran to this issue but I welcome any other solutions!
The problem as stated in my question is caused by the files I want to include in my package being older than the files in my project. So I needed to find a way to update the last modified date.
I found out that there is a "Touch" task that will do exactly that: http://msdn.microsoft.com/en-us/library/37fwbyt5.aspx
So this is what I finally did in my script:
<ItemGroup>
<Files Include="F:\Files For Sites Deployment\xxx\**\*" />
</ItemGroup>
<PropertyGroup>
<CopyAllFilesToSingleFolderForMsdeployDependsOn>
TouchIncludeFiles;
CustomCollectFiles;
$(CopyAllFilesToSingleFolderForMsdeployDependsOn);
</CopyAllFilesToSingleFolderForMsdeployDependsOn>
</PropertyGroup>
<Target Name="TouchIncludeFiles">
<Touch Files="@(Files)" ForceTouch="true"></Touch>
</Target>
<Target Name="CustomCollectFiles">
<ItemGroup>
<_CustomFiles Include="@(Files)" />
<FilesForPackagingFromProject Include="%(_CustomFiles.Identity)">
<DestinationRelativePath>%(RecursiveDir)%(Filename)%(Extension)</DestinationRelativePath>
</FilesForPackagingFromProject>
</ItemGroup>
</Target>