How do I detect the first time a ClickOnce-deployed application has been run?

Include an extra file in your ClickOnce install called justInstalled.txt (or something). Chedk for that file when the app starts. If you find it delete it and run any code for your first run of that deployment. The file will stay missing until the next deployment/upgrade.

Yes the IsFirstRun is reset for each program version...

This is the except from Microsoft:

The value of this property is reset whenever the user upgrades from one version to the next. If you want to perform an operation only the very first time any version of the application is run, you will need to perform an additional test, such as checking for the existence of a file you created the first time, or storing a flag using Application Settings.

which more or less answers you question...