<p>If I understand correctly, <code>ClickOnce</code> only checks for prerequisites with the first install of an application through the setup.exe file that contains the prerequisite information. If the user opens the app in the future it will check for new versions, but it does not launch the setup.exe again, thus not checking for any NEW prerequisites that might have been added.</p>

<p>Is there any way to force ClickOnce to check the prerequisites again or does anyone have a good solution without asking the user to run the <code>setup.exe</code> again?</p>

Unfortunately, your users will have to re-run the setup.exe to check and install all the new prerequisites that you have added.
Applications deployed using ClickOnce only check for application updates (if enabled), not prerequisites as it's the bootstrapper's job to make sure all dependencies are installed before the application is installed.
I found this at
Microsoft's site
:
The Setup.exe (bootstrapper) is
  responsible for installing all
  dependencies before your application
  runs. This bootstrapper runs as a
  separate process that is independent
  of the ClickOnce run-time engine.