That information isn't available on an internal search.
You can get that a few different ways though.
It's available in SuiteTalk using the getDeleted operation
It's available via an external database query using SuiteConnect (ODBC, JDBC or ADO.net)
If you can start from now an easy hack is as follows:
create an After Submit User Event script that runs on record creation. If the record doesn't have an external id push the namespaced netsuite internal id into that field. I've found it's generally a good idea to prefix your external ids with the system of origin.
Now you can derive your internal ids from the external id. This doesn't help if you also have actual externalids but may suit your use case.
You can also fairly easily roll your own and create an after submit user event script that populates a custom record with the type and internalid of the deleted record. It's generally the way I go. Particularly if you are driving other suitescripts or workflows in your Netsuite account from the deletion data
Finally, though I haven't done this in years, it's quite possible to run a SuiteTalk query from SuiteScript. You just have to save the credentials (not in the clear) and construct the appropriate SOAP message.