Ha pasado mucho tiempo desde la pregunta inicial, pero tuve el mismo problema y encontré una solución.
Escribí una aplicación cuyo objetivo es permitir que cualquier persona cree archivos lnk desde cualquier sistema operativo. Empecé a escribirlo en bash y luego lo convertí en C (las fuentes están disponibles).
Todavía está fresco, por lo que, excepto yo, nadie lo probó todavía, pero puedes echarle un vistazo aquí:
http://www.mamachine.org/mslink/index.en.html