You can add the claiming code into your XML, but as you've discovered, it has to be in the right place. Make sure you place the code in any episode's description. Preferably at the end (it looks ugly at the top of the description). It might look something like this between the tags:
<description>This is my podcast about what I like. I like it very much. Thank you for listening!
<a href="http://www.podcastalley.com/"> Podcast Alley Claim Code </a> {podshow-9ebd7c73416a49dea6cfbe855fafd23d}</description>
And don't forget to re-upload that baby.
As far as getting your search issue fixed, I guess I'd get your feed claimed and migrate to Feedburner first. I suspect you'll end up needing someone on PCA's side of things to help you get that old feed redirected to the new one.
I cannot stress this enough! Please note for your own sanity: You really should be posting PodcastAlley technical questions in the Podcast Alley Help forum! The staff, such as it is, monitors that forum the most frequently, so you're more likely to get official support there than here! I'm just a passerby giving you some suggestions, and that's about the only help you can expect to get by posting here. You really should go to the official forum!
Best of luck,
Eric