OK or Cancel Popup in AddPage:BeforeRecordAdded

This would not be possible as BeforeRecordAdded event is executed on the server.
Your best bet is to modify submit button behaviour adding a javascript code with confirm() function call.

Realize that, Mission Impossible..
My custom validation (which usually would be done in BeforeRecordAdded) requires access to the database.

If a particular situation exists, then give the user the option of continuing or cancelling the add. But the validation doesn't have to be triggered by the Save button (BeforeRecordAdded), it could be triggered when fields are being entered, much like any javascript (client) built-in validation.
One way of doing this in javascript (browser) will require a custom ajax exchange, a custom validation actually involving the server. But I am being a bit general, and I need a solution today, and will accept any sort of idea that'll work without causing ongoing maintenance issues.
In this particular case I give the user the option of allowing a duplicate (partial) key. So the minimum I need is when the user enters a value into a control, for the control to change to a warning colour if the value already exists in the database, but still allow the transaction to complete either way when Saved.
In the javascript API are there any new methods I could use?