How to comply with this guideline for submitting an application to the Software Center?
The clause is meant to inform you, the developer, that it is your responsibility (obligation to use that terminology) to ensure your application runs on the supported versions of Ubuntu, not Canonical's. You are not forced to test on all versions, but it is in your best interest to ensure it runs on the latest Ubuntu release and prior versions.
For the purposes of the software center and paid applications, you should test 11.10, 11.04 and 10.10. You always have the option of only supporting the latest version if you wish and just need to inform the reviewer of that requirement when submitting your application.
In the case of ARB apps (FLOSS apps) you will want to ensure compatibility with all supported releases.
I hope that helps clarify the terms a bit better.
To answer your first question, it is feasible, if time consuming. As you probably already read:
Normal Ubuntu releases are supported for 18 months. Previous Ubuntu LTS (Long Term Support) releases are supported for 3 years on the desktop and 5 years on the server. Starting with Ubuntu 12.04 LTS, LTS releases will be supported for 5 years on both the desktop and the server. - https://wiki.ubuntu.com/Releases
So, yes, as of November 2011, you must test with
- 8.04 (server edition)
- 10.04
- 10.10
- 11.04
- 11.11
Using a virtual machine would be one way. Another way would be to download the .iso files for each release's LiveCD, then use your bootloader to create an entry for each .iso. You can find instructions here to add entires to /etc/grub.d/40_custom which will survive kernel upgrades.
Note that 'versions' does not mean architectures. You do not need to test on both 32- and 64-bit architectures, so there are only five tests you need to run, not 10 :)