How does UDP track connections

A stateful firewall can track UDP. It just creates an established connection for UDP once it has seen a packet coming from a masqueraded internal machine to an IP address on the internet. Any responding traffic is automatically forwarded to the internal machine.

So, iptables basically remembers the port number that was used for the outgoing packet (what else could it remember for a UDP packet?),

I am pretty sure for UDP the source and destination ports and addresses are stored.

If you want to inspect the state tables install conntrack and/or netstat-nat.

(What would happen, if I accidentally tried to start a service on that port within the timeframe - would that attempt be denied/blocked?)

Since you are using OUTPUT and INPUT your are talking about local services. The port is already used I don't believe your system will allow you to start up another service since something is already listening on that port. I guess you could stop the first service and start another if you really wanted to though, in that case the response would probably get to your service. What the service does with the packet depends on what the contents of the packet is, and what service it is.