Despite trying most of the solutions here this issue persisted for me.

A while back I had unsubscribed to Github copilot but had not uninstalled the extension. I tried uninstalling the copilot extension as the dialog kept bugging me, and suddenly VSCode found my Python interpreter / kernel. I am assuming there is some weird magic going on with the way copilot uses the selected interpreter and when the subscription not present the whole thing silently fails.