Is the shortcut pointing to a FOLDER or an actual FILE?
If it's a FILE, then try adding that UNC location to your TRUSTED SITES in Internet Explorer. Weird I know but it does work. If it's to a drive (like Z:\drive) then add Z:\ to your Trusted Sites in IE
If it's to a folder and you say somethings it works and sometimes it doesn't, try this registry setting on your WORKSTATION first and if it doens't work, try it on the SERVER as well. I've done this for two different client sites of mine and it has fixed the problem. Though I was geting a message that says "insufficient system resources" but it had a similar characteristic like yours where it will work one day but later on the day, the user can't access the network share/drive.
You can always remove it if it doesn't work.
=============================================
Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\Memory Management]
"PagedPoolSize"=dword:ffffffff
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\VSApiNt\Parameters]
"EnableSystemView"=dword:00000001
=============================================