We have been plagued by this issue for a long, long time. I've finally come across the solution, and I had to give back to the community by sharing.
If you look up "invalid action attachment notes dynamics crm" you'll find people saying to restart the async service or run the WRPC token generator tool and restart IIS. None of that helped me. It isn't even a server side issue.
What DID help though, was going to the affected user's PC, and going to Tools -> Internet Options and deleting temporary files - but you must UNCHECK "Preserve Favorites website data" if CRM is listed in your favorites.
For users who don't have CRM in their favorites, they shouldn't need to uncheck that box - and you'll probably notice users who don't have CRM in their favorites probably don't have this issue.
I've spent tons of time trying to figure this out, always assuming it was a server side issue. I've posted on here several times about it, and got no useful responses. Hopefully this post helps someone!!
*This post is locked for comments