adding block region inside of menu section
Part of the problem is that regions aren't really what you're looking for here. Drupal regions are just areas of the page, and you set content to appear in a given region. One way of utilizing regions for this would be to have a menu region defined in your theme's .info file, and then putting the menu and the search block in that region. I'm betting that's not really what you're after, though, because it doesn't result in very clean code.

There are two other options that I can see. One is to create your own theme callback for menus so that instead of calling theme('links', array(...)), you're calling theme('your_new_theme_callback', array(...)). You can define different variables for this theme, and one of them could be for the search block.

Of course, because this is Drupal, there's already someone who's gone "Man, I really want blocks in my menu and there's no nice way to do that in Drupal" and created a module. The Menu Attach Block module lets you attach a block to your menu. I've not used it before so I'm not 100% sure how to implement it in the way you're looking for. It doesn't look like you'd have to change your code at all, I don't think, because it looks like the module overrides theme_link() for you.

Does that make sense? If you want more details, let me know!