The HTML might look like this, the important attribute: doClientPaging="false" this takes care that the same query is fired to the server and its not assumed that the client (the store) does the paging on the old data.

<div dojoType="ServerPagingReadStore" jsId="serverPagingStore" url="stores/QueryReadStore.php" requestMethod="get" doClientPaging="false"></div>
<input dojoType="dijit.form.ComboBox" store="serverPagingStore" pageSize="10" />
	

		dojo.require("dojox.data.QueryReadStore");
		dojo.provide("ServerPagingReadStore");
		dojo.declare("ServerPagingReadStore", dojox.data.QueryReadStore, {
			fetch:function(request) {
				request.serverQuery = {q:request.query.name, start:request.start, count:request.count};
				return this.inherited("fetch", arguments);
			}
		});