After some investigations in the past this seems to be a timing issue. To me it looks like m2e is adding libraries to the classpath container after they got downloaded, but the validations ran before and therefore weren't able to find that class.
So my assumption is that we don't revalidate this after the right JARs got added to the project classpath. Maybe we don't listen to the right event, maybe m2e isn't firing up the right one, don't know.
The bad thing is that this is not easy to reproduce. The best chance is to delete the local Maven repository, so that m2e/Maven needs to download everything again (and maybe have a slow connection for that).