NEI plugins got merged into a single download quite a while ago. If you have them separate you are probably using some rather old version:
I think this will solve my problem as well. When I installed NEI and read "All plugins for NEI now together." I made the wrong assumption that I didn't need to install anything additional. But after reading that page again, I see that I still need to install the combined plug-in. So the error was completely my fault.