I'm working with a bit of Python that looks like this:

HOST = '127.0.0.1'
PORT = 43434
single = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
try:single.bind((HOST, PORT))
except socket.error as e:# Print an error, exit.

While it's been functioning well in the past, we now get the error [Errno 98] Address already in use. The SIGINT handler closes the socket connection, so I'm not sure how it got in that state, but for now I'm just trying to fix it.

Both lsof and netstat say there's nothing using that port:

[$]> sudo netstat -an | grep 43434
[$]> sudo lsof -i :43434

TIME_WAIT is set to 60 seconds, according to /proc/sys/net/ipv4/tcp_fin_timeout, but the error occurs even hours after last run successfully.

I've tried (temporarily) setting REUSEADDR (via single.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)), but that appears to have no effect.

What in tarnation is going on? Will I ever be able to use this port again without having to reboot the machine?

Try this:
tcpkill -i eth0 port 43434