We actually had the similar issues with deploying printers and Windows 10. It would be very inconsistent, but a second login would always do the trick.
What we actually found out is that the mapping seemed to fail the first time, but never on the second. We now use a small vbscript that maps the printer twice (and sets it as default if you so wish). It's a bit silly that that is the case, but at some point if it just works you go with it. It's pretty much worked 100% for the last couple of years and iterations of Windows 10. This is what we use (save it as .vbs):
Set wshNetwork = CreateObject("WScript.Network")
on Error Resume Next
'Deletes all network printers
Set clPrinters = WshNetwork.EnumPrinterConnections
On Error Resume Next
For i = 0 to clPrinters.Count - 1 Step 2
wshNetwork.RemovePrinterConnection clPrinters.Item(i+1), true
Next
Dim oNet
Set oNet = CreateObject("WScript.Network")
oNet.AddWindowsPrinterConnection "[PRINTER QUEUE NAME]"
oNet.AddWindowsPrinterConnection "[PRINTER QUEUE NAME]"
Dim obj
ShellSet objShell = WScript.CreateObject( "WScript.Shell" )
objShell.Run "rundll32 printui.dll,PrintUIEntry /y /n ""[PRINTER QUEUE NAME]"" "
Set objShell = Nothing