Has any one seen something like this?
Yes. You do this a lot on the web, but some windows applications do this as well. Most common on internet reliant applications such as instant messaging services. For examples, check out the ICQ and MSN Live clients.
It is not usual to see ads and banners in applications that customer's pay. Instead "free" software use them and in those cases you usually are able to opt-in payment to get rid of them.
How can it be done?
The basic functionality you need to do is explained in the figure below:
+--------------+ +----------+
| Ad Providing | The Internet | Your App |
| Server | | |
| | 1. Request Ads | |
| |<---------------| |
| | | |
| | 2. Send Ads | |
| |--------------->| |
+--------------+ +----------+
The web server needs to keep a list of ads that it can return to the app. Your application needs to request and receive ads from the web server. The specifics on how to do this depends on the protocols used (e.g. JSON documents over HTTP requests) and there are lots of ways to implement. I'd suggest you check out available ad providers, sign up to retrieve ads and check out their protocols so you can implement it to your app.
How can I interest the companies to sponsor the app?
If you manage to get lifetime sponsors, you could hardcode the images or messages into the application.
If you want to deal with periodical sponsorships you will need to build a web server or use a third-party ad provider that provides the ad images and messages for your application.
I'd recommend you check out ad or banner networks that may work for you. The ones I can think off the top of my head are Google Ads and you can do a google search for banner networks to search for that and information on how to generate some revenue from banners.
The best banners however are the ones that are most relevant to your audience, so be mindful about what banners that you allow into your application.
Hope this clears up for you.