Yahoo! Search has recently published a web service. Sadly, they did not implement it using SOAP and there is no .Net example in their download. Fear not though as I have done the dirty work for you and posted a C# example on my Downloads page.
I don't claim it is perfect, but it is not far off.