game.Players.PlayerRemoving:connect(function(player) is only firing sometimes?

I don't know why it wouldn't work all the time, but I guess you could use ChildRemoved instead?http://wiki.roblox.com/index.php?title=API:Class/Instance/ChildRemoved

There might be another answer, but that's all I could think of.

This is because functions connected to PlayerRemoving do not execute when the last player in the server leaves.

To get around this, you must utilize BindToClose(). BindToClose allows Roblox to call callback functions right before shutting down (which it will attempt to do when the last player leaves).

Here's how you should generally handle players leaving:

local function playerLeaving(player)
    -- handle player leaving here
end

game.Players.PlayerRemoving:Connect(playerLeaving)

game:BindToClose(function()
    for _, player in pairs(game.Players:GetPlayers()) do
        playerLeaving(player)
    end
end)