servers_controller.rb
class ServersController < ApplicationController
  def index
    @servers = Server.paginate(:page => params[:page], :per_page => 20, :order => 'device_id ASC')
    respond_to do |format|
      format.html 
      format.xml  { render :xml => @servers }
    end
  end

  def search
    @servers = Server.paginate(:page => params[:page], :per_page => 20, :order => 'device_id ASC', :conditions => ["hostname like ?", "%"+params[:keyword]+"%"])
   render :action => 'index'
  end
end

Severs view index.html.erb

上記省略
<%= will_paginate @servers %>

これでindexは問題ないのですが、searchの方が次ページに行くと、
ActiveRecord::RecordNotFound (Couldn't find Server with ID=search):
  app/controllers/servers_controller.rb:26:in `show'

showは何も変更してません。
  def show
    @server = Server.find(params[:id])

    respond_to do |format|
      format.html # show.html.erb
      format.xml  { render :xml => @server }
    end
  end

search後の1ページは何ら問題なく、検索も正常でshowも表示されます。
次ページ以降にエラーが出ます。
def searchもしくはviewに変更箇所はあるでしょうか？

次ページ以降をクリックした先のURLは、パラメータに?page=2などと
表示があると思うのですが、それに続けて&keyword=hogeのようにkeywordのパラメータも引き継がれていますか？
引き継がれていないのであれば、params[:keyword]が見つからずエラーになっているのではないかと思います。

ご指摘の通りクリック先には?page=2のあとに&keyword=hogeのようなパラメータはありません。
それで引き継がせ方なのですが、:page => params[:page]がすでにある上に、どのようにparams[:keyword]
を渡せばよいのでしょうか？

ちょっとググってみたところ
<%= will_paginate @servers, :params=>{:keyword=>params[:keyword]}%>でいけるみたいですよ。

参考
http://blog.livedoor.jp/maru_tak/archives/50611217.html

<%= will_paginate @servers, :params=>{:keyword=>params[:keyword]}%>でいけました。
ありがとうございます。