Ok. After a full day of fun and debugging, I finally realised the problem.
The gacutil -i installs to C:\Windows\Microsoft.NET\assembly for .NET 4.0+, and apparently VisualCron doesn't recognize assemblies in this folder.
Instead I had to find a .NET 2.0 version of the assembly and install this using gacutil.exe (which is installed to C:\Windows\assembly) and voila, now it's visible in VisualCron.
This sounds to me like a bug in VisualCron?
I can back this up using screenshots if need be. :)
Best regards,
René