How can I test windows programs in the cloud?
I'm not sure of any services like that, but it sounds to me that you want to use a virtual machine such as VMware or VirtualBox.
You can use Windows Azure VM Role to get your VM setup in the cloud. On the VM you have to install all the required softwares. Coming to your point, If you look at http://www.microsoft.com/VHD, you can get trial VPCs for your use that you can then either run on your own machine or host in cloud.
You can use Amazon Elastic Cloud
http://aws.amazon.com/ec2/instance-types/
"Amazon Elastic Compute Cloud (Amazon EC2) provides the flexibility to choose from a number of different instance types to meet your computing needs. Each instance provides a predictable amount of dedicated compute capacity and is charged per instance-hour consumed."
You have to use your own OS, however. Amazon only provides server OS'es out of the box