I am having that same issue, but so far the only thing that has helped a little is the new URL structure that we rolled out which doesn't have any dynamic characters in it anymore, just static looking.
Look at deeplinking and your sitemaps. Also look at your menu structure, if it takes many clicks for you to get to the lower pages it will be harder for the spiders too. Does your menu use javascript as this may prevent the spiders accessing all pages too.
Submit a RSS FEED to yahoo, or a sitemap, or both as it will make it easier for yahoo's spider to find your pages....
One of the best strategies I know is to make a shallow site. I've had way better indexing on sites that are only 3 tiers deep. This seems to work for Google as well, I just build wider rather then deeper. I also agree with MikeWarrior, if your site is beyond restructuring then it's best to submit an RSS feed and a yahoo friendly sitemap.
Build Back Links for your site's main page + also build back links for inner pages. Hopefully, this will help.