Please find my answers(in normal text) against each of the questions(in italics) asked.
"1) Do you think the search panel should be visible all the time (ie displayed on top of my result grid) or available in a separate form (which would let me use more place for all the controls)"
Display on top of result grid as this leaves extra horizontal space to display search results and thereby to display more columns of search data without scrolling horizontally.
"2) Do you think it's better to display all the search criteria, or to let the user click on 'advanced' if he wants to see/use more criteria"
Display all available criteria but in a tabbed fashion. i.e. categorize input search fields into categories and have a tab for each category.
"3) How would you organize the criteria? by usage frequency, or rather by area (ie. criteria related to user, to location, to time, etc.)"
Organize 'by area' because different people like using different criteria.
Each criteria would have tab of it's own. But organize the tabs in the order of 'more popular' to 'less popular' as you think. In your case tabs may be 'By Name'(containing fields first name, middle name, last name, mother maiden name, nick name, father's name etc), 'By Location' (place name, county name, district name, state name, country name etc)
and so on until the advanced tab(where you'd put least used fields).
"4) Where should I put the 'Search' button? next to the more common search controls, or at the bottom, or both?"
Put the input fields of search as discussed above in a tabbed fashion categorizing them based on 'type of field'(I'll refer to this area as search grid). Then put action buttons such as 'Search', 'Clear/Reset' just below the search grid aligning to the center(I'll refer to this area as button grid).Then put the search result pane below the button grid as more horizontal area is available for display so that maximum columns can be displayed at once.