Regarding the software portion of your due diligence see
this:
http://www.fdic.gov/news/news/financial/2004/fil12104.htmlGet other people involved (especially IT) in the project, they'll have questions that you wouldn't ask.
Make a table or spreadsheet and compare what each software package includes, such as:
How does it detect suspicious activity?
What does it include in its search/rules/queries/reports? (i.e., wire transfers, monetary instrument log, cash deposits, CTRs, cash in\cash out, patterns of activity, customer profile, etc.)
Does it have an OFAC module? Is it automatically downloaded when updates occur, or do you have to download it? Can it perform 314a searches, PEPs?
Does the system include automated SAR & CTR filings?
Have a demo of each software product.
Is the software user friendly?
Background of the company.
Costs (initial & annual)
Does initial set-up include customization, if needed?
Contact other banks that use the product for their assessment (The only problem here is that they provide you with the list, which would probably exclude any banks that had problems with installation.)
Compare the benefits and shortcomings of each product and make a decision.
I'm sure that this list not all-inclusive, but I hope it's a start.