I had to tackle this issue at one of my clients and the way I solved this issue was by creating a table and putting the PlaceHolderSearchArea in that <TD> and aligned the <TD>

<table style="width: 100%; float:right;">
    <tr >
     <td width="100%"></td>
     <td id="SearchBox" align="right" style="text-align:right;">
       <asp:ContentPlaceHolder id="PlaceHolderSearchArea" runat="server">
        <SharePoint:DelegateControl runat="server" ControlId="SmallSearchInputBox"/>
       </asp:ContentPlaceHolder>
     </td>
    </tr>
</table>

This did the trick for me but I really did not have much time to better understand what was causing this issue and I came accross the answer in Heather's post. (for those of you who have not visited her site yet please do it's a gold mine of information.)

Heather found out that there was an empty table cell to the right of the search inputs with a width set to 100%. So you need to take care of that in order to move around your search box. To get her solution(CSS Code) to this click on the following link which will take you to her post about this topic.

SharePoint CSS Trick: Align your Search Inputs

<coskun\>

(I liked Lawrence's signature. he signs his name as a html tag and I think I'll use this as well. Pretty geeky and I like it :)