I would recommend everyone here to also take a look at the Yahoo API. It is far superior to the MSN API. You can find it at
http://developer.yahoo.net/
First, they actually provide all the searching capability that MSN provides, plus extra functionality like image search. Second, they have great language support. Third, they have integration with other sites like Flickr. Fourth, they are very responsive to bug reports, ideas and even have a great API blog that's very active with their improvements, apps being built, etc.
Microsoft has simply dropped the ball with this API. They delivered a product late in the game, and when they did it was lacking in all ways.
Good luck.