There are a few sites out there which have the .LNK format details as a result of reverse-engineering but it looks fairly complex to parse.
I can't think of any reason why using Interop.Shell32.dll would be a problem.
Not sure if you've already been playing with it but I found this along the way...
public string GetShortcutTargetFile(string shortcutFilename)
string pathOnly = System.IO.Path.GetDirectoryName(shortcutFilename);
string filenameOnly = System.IO.Path.GetFileName(shortcutFilename);
Shell32.Shell shell = new Shell32.ShellClass();
Shell32.Folder folder = shell.NameSpace(pathOnly);
Shell32.FolderItem folderItem = folder.ParseName(filenameOnly);
if (folderItem != null)
Shell32.ShellLinkObject link = (Shell32.ShellLinkObject)folderItem.GetLink;
return ""; // not found