(user testing here)
In both examples Fill region its active, that's causing that behavior.

I have the SelectShortestPath with FillRegion mapped to other mose+hotkey combo. I used that to select the faces from Step #2
As you can see in this image, after I have selected those faces, I deleted them, and then I use SelectShortestPath (without FillRegion) and that's where the bug happens.

http://edge-loop.com/images/blender/bugtracker/SelectShortestPath_Bug_279_xtra.jpg

the operator that you are using there its "Pick shortest path" (bpy.ops.mesh.shortest_path_pick)
, not "select shortest path"( bpy.ops.mesh.shortest_path_select() )

i can force the behavior but need to manually select the right operator to keep track of the options previously enable. I couldn`t do it with the standard tools and Blender's shortcuts.

at this point I cant add any more useful information, the developers would evaluate this better.

Thanks on the explanation!

Thing is I use blender daily with this custom config. And there definitely was something changed ~month ago that introduced this behavior.

I was able to make it work even with "Pick shortest path" (bpy.ops.mesh.shortest_path_pick)
What I had to do was, in the InputEditor, to check-then uncheck the checkbox beside "Fill Region".

After doing that, it forced the command to be like this:
bpy.ops.mesh.shortest_path_pick(use_fill=False, index=69)

As opposed to what I had before:
bpy.ops.mesh.shortest_path_pick(index=69)

Here's an image to illustrate it better what I had done in the InputEditor:
http://edge-loop.com/images/blender/bugtracker/SelectShortestPath_Bug_279_xtra2.jpg

Thanks on helping me sort it out. All is good in blender world again :)
Although there still remains the fact that something was introduced recently that breaks this custom hotkey that was working fine before. Potentially other people that remapped that might run into the same problem.

Just wanted to confirm it's fixed!