I'm not sure I follow exactly what order you removed/added NAT entries, but it sounds to me like the xlate for that server was still in the xlate table even when the command was removed. This will happen unless the xlate was cleared for that specific device. If you are CLI, you would use the 'clear xlate local/foreign...etc...' commands. The default for an xlate timeout is 3 hours. You can verify this by issuing 'show running-config timeout'. This will also show connection timeouts. It is possible that the connection was kept alive and timed out after 3 hours. I believe the default for connection timeout is 1 hr, however.
Anyway, again, not sure I understand fully what happened, but it does sound like either the xlate timeout or conn timeout values.
Thanks,
Jeff