簡単なのはShell32.dllをCOMとして参照設定し、
using Shell32;
で、Z:\Hoge.lnkのリンク先を得るコードはこんな感じ。
ShellFolderItemを直接得る方法があればいいんだけど、それは分からん。

Shell sh = new Shell();
Folder f = sh.NameSpace(@"Z:\");
foreach (ShellFolderItem i in f.Items())
{
if (i.IsLink && i.Path == @"Z:\Hoge.lnk")
{
Console.WriteLine(((ShellLinkObject)i.GetLink).Target.Path);
}
}