Some time has passed (new baby girl!) and I sat down with your advice to find the source of the problem. Moving the (genuine hiwin) carriages manually I found some binding in them at times.
Looking in to the problem I found that each of my carriages were missing 1 ball bearing. After adding the bearings, the problem has been completely solved.
My advice to anyone facing this problem is don't give up! and try practical tests like the ones David has mentioned. It's a frustrating experience but there is a solution!
Thanks again dc42!