[Desire Android Development] lenny_kano:
I replaced the recent apps button in previous miui-au releases, but the same principal would apply. Recent apps works via long press on home soft key (maybe only after i changed it?) anyway so figured it wasn't necessary. Following is the code for SystemUI\res\layout\navigation_bar.xml

<?xml version="1.0" encoding="utf-8"?>
<com.android.systemui.statusbar.phone.NavigationBarView android:background="#ff000000" android:layout_width="fill_parent" android:layout_height="fill_parent"
xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:systemui="http://schemas.android.com/apk/res/com.android.systemui">
<FrameLayout android:id="@id/rot0" android:layout_width="fill_parent" android:layout_height="fill_parent">
<LinearLayout android:orientation="horizontal" android:id="@id/nav_buttons" android:clipChildren="false" android:clipToPadding="false" android:layout_width="fill_parent" android:layout_height="fill_parent" android:animateLayoutChanges="true">
<View android:visibility="invisible" android:layout_width="40.0dip" android:layout_height="fill_parent" android:layout_weight="0.0" />
<com.android.systemui.statusbar.policy.KeyButtonView android:id="@id/back" android:layout_width="80.0dip" android:layout_height="fill_parent" android:src="@drawable/ic_sysbar_back" android:layout_weight="0.0" android:contentDescription="@string/accessibility_back" systemui:keyCode="4" systemui:glowBackground="@drawable/ic_sysbar_highlight" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="fill_parent" android:layout_weight="1.0" />
<com.android.systemui.statusbar.policy.KeyButtonView android:id="@id/home" android:layout_width="80.0dip" android:layout_height="fill_parent" android:src="@drawable/ic_sysbar_home" android:layout_weight="0.0" android:contentDescription="@string/accessibility_home" systemui:keyCode="3" systemui:glowBackground="@drawable/ic_sysbar_highlight" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="fill_parent" android:layout_weight="1.0" />
<com.android.systemui.statusbar.policy.KeyButtonView android:id="@id/recent_apps" android:layout_width="80.0dip" android:layout_height="fill_parent" android:src="@drawable/ic_sysbar_recent" android:layout_weight="0.0" android:contentDescription="Search" systemui:keyCode="84" systemui:glowBackground="@drawable/ic_sysbar_highlight" />
<com.android.systemui.statusbar.policy.KeyButtonView android:id="@id/menu" android:visibility="invisible" android:layout_width="40.0dip" android:layout_height="fill_parent" android:src="@drawable/ic_sysbar_menu" android:layout_weight="0.0" android:contentDescription="@string/accessibility_menu" systemui:keyCode="82" systemui:glowBackground="@drawable/ic_sysbar_highlight" />
</LinearLayout>
<LinearLayout android:orientation="horizontal" android:id="@id/lights_out" android:visibility="gone" android:layout_width="fill_parent" android:layout_height="fill_parent">
<ImageView android:layout_width="80.0dip" android:layout_height="fill_parent" android:layout_marginLeft="40.0dip" android:src="@drawable/ic_sysbar_lights_out_dot_small" android:scaleType="center" android:layout_weight="0.0" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="fill_parent" android:layout_weight="1.0" />
<ImageView android:layout_width="80.0dip" android:layout_height="fill_parent" android:src="@drawable/ic_sysbar_lights_out_dot_large" android:scaleType="center" android:layout_weight="0.0" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="fill_parent" android:layout_weight="1.0" />
<ImageView android:layout_width="80.0dip" android:layout_height="fill_parent" android:layout_marginRight="40.0dip" android:src="@drawable/ic_sysbar_lights_out_dot_small" android:scaleType="center" android:layout_weight="0.0" />
</LinearLayout>
<View android:layout_gravity="top" android:id="@id/deadzone" android:clickable="true" android:layout_width="fill_parent" android:layout_height="@dimen/navigation_bar_deadzone_size" />
</FrameLayout>
<FrameLayout android:id="@id/rot90" android:paddingTop="0.0dip" android:visibility="gone" android:layout_width="fill_parent" android:layout_height="fill_parent">
<LinearLayout android:orientation="vertical" android:id="@id/nav_buttons" android:clipChildren="false" android:clipToPadding="false" android:layout_width="fill_parent" android:layout_height="fill_parent" android:animateLayoutChanges="true">
<com.android.systemui.statusbar.policy.KeyButtonView android:id="@id/menu" android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="40.0dip" android:src="@drawable/ic_sysbar_menu_land" android:layout_weight="0.0" android:contentDescription="@string/accessibility_menu" systemui:keyCode="82" systemui:glowBackground="@drawable/ic_sysbar_highlight_land" />
<com.android.systemui.statusbar.policy.KeyButtonView android:id="@id/recent_apps" android:layout_width="fill_parent" android:layout_height="80.0dip" android:src="@drawable/ic_sysbar_recent_land" android:layout_weight="0.0" android:contentDescription="Search" systemui:keyCode="84" systemui:glowBackground="@drawable/ic_sysbar_highlight_land" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="fill_parent" android:layout_weight="1.0" />
<com.android.systemui.statusbar.policy.KeyButtonView android:id="@id/home" android:layout_width="fill_parent" android:layout_height="80.0dip" android:src="@drawable/ic_sysbar_home_land" android:layout_weight="0.0" android:contentDescription="@string/accessibility_home" systemui:keyCode="3" systemui:glowBackground="@drawable/ic_sysbar_highlight_land" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="fill_parent" android:layout_weight="1.0" />
<com.android.systemui.statusbar.policy.KeyButtonView android:id="@id/back" android:layout_width="fill_parent" android:layout_height="80.0dip" android:src="@drawable/ic_sysbar_back_land" android:layout_weight="0.0" android:contentDescription="@string/accessibility_back" systemui:keyCode="4" systemui:glowBackground="@drawable/ic_sysbar_highlight_land" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="40.0dip" android:layout_weight="0.0" />
</LinearLayout>
<LinearLayout android:orientation="vertical" android:id="@id/lights_out" android:visibility="gone" android:layout_width="fill_parent" android:layout_height="fill_parent">
<ImageView android:layout_width="fill_parent" android:layout_height="80.0dip" android:layout_marginTop="40.0dip" android:src="@drawable/ic_sysbar_lights_out_dot_small" android:scaleType="center" android:layout_weight="0.0" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="fill_parent" android:layout_weight="1.0" />
<ImageView android:layout_width="fill_parent" android:layout_height="80.0dip" android:src="@drawable/ic_sysbar_lights_out_dot_large" android:scaleType="center" android:layout_weight="0.0" />
<View android:visibility="invisible" android:layout_width="fill_parent" android:layout_height="fill_parent" android:layout_weight="1.0" />
<ImageView android:layout_width="fill_parent" android:layout_height="80.0dip" android:layout_marginBottom="40.0dip" android:src="@drawable/ic_sysbar_lights_out_dot_small" android:scaleType="center" android:layout_weight="0.0" />
</LinearLayout>
<View android:layout_gravity="left" android:id="@id/deadzone" android:clickable="true" android:layout_width="@dimen/navigation_bar_deadzone_size" android:layout_height="fill_parent" />
</FrameLayout>
<View android:id="@id/rot270" android:visibility="gone" android:layout_width="fill_parent" android:layout_height="fill_parent" />
</com.android.systemui.statusbar.phone.NavigationBarView>

Then all thats needed is changing SystemUI\res\drawable-hdpi\ic_sysbar_recent.png and ic_sysbar_recent_land.png to be a search icon (attached).

Hope this helps.