Another option to help reduce the overhead caused by slow tests is to store test results in the database. Each time a page is requested, you would pull up a specific record from the wp_options table where you stored the results of the last test. Based on the result, you could decide whether or not you needed to run tests again. Querying the database does incur some overhead, but it may be significantly less overhead than running through an entire gauntlet of testing functions.
There are many different options available to you when choosing how to test your plugin. The requirements really vary depending on the nature of the code you have used, but we've given you a good starting toolbox for how to test for some of the most common conditions.
However, valid tests are not the only thing your plugin needs before it is cleared for launch. You need to examine your configuration and the documentation before you push your plugin out of the nest.