Permissions in triggers when using cross database certificates
The problem here is that while the Certificate links the stored procedure in DatabaseA with the User in DatabaseB that has INSERT permissions on the two tables, the Trigger on the table being inserted into directly from the stored procedure is another module in the chain, and permissions acquired from Certificates do not pass along to other modules in a chain. Meaning, the Certificate allowed the Stored Procedure to insert into the table via the User, and even execute the Trigger. But, no permissions have been given to the Trigger to do anything related to objects (doing something like SELECT 1; would work).

In this case, permissions need to be given to the Trigger, via that same Certificate, so that it can take whatever actions are necessary. This can be accomplished, at the very least, by counter-signing the Trigger. And you do that by executing ADD COUNTER SIGNATURE TO [TriggerSchema].[TriggerName] BY CERTIFICATE ...;. After that, it should just work, even without direct INSERT permission for the Certificate-based User on the table being inserted into by the Trigger.

The example code below reproduces the problem, fixes the problem by adding a counter signature, but does not grant INSERT permissions to the trigger-populated table.

CLEANUP

USE [master];
GO
IF EXISTS (SELECT 1 FROM [sys].[databases] WHERE [name] = N'DatabaseA')
BEGIN
    PRINT 'Dropping [DatabaseA] DB...';
    ALTER DATABASE [DatabaseA] SET OFFLINE WITH ROLLBACK IMMEDIATE;
    ALTER DATABASE [DatabaseA] SET ONLINE;
    DROP DATABASE [DatabaseA];
END;

IF EXISTS (SELECT 1 FROM [sys].[databases] WHERE [name] = N'DatabaseB')
BEGIN
    PRINT 'Dropping [DatabaseB] DB...';
    ALTER DATABASE [DatabaseB] SET OFFLINE WITH ROLLBACK IMMEDIATE;
    ALTER DATABASE [DatabaseB] SET ONLINE;
    DROP DATABASE [DatabaseB];
END;

IF (SUSER_ID(N'JohnnyLunchbucket') IS NOT NULL)
BEGIN
  PRINT 'Dropping [JohnnyLunchbucket] Login...';
  DROP LOGIN [JohnnyLunchbucket];
END;

IF (OBJECT_ID(N'tempdb..#CertInfo') IS NOT NULL)
BEGIN
  PRINT 'Dropping [#CertInfo] Temp Table...';
  DROP TABLE #CertInfo;
END;


SETUP

USE [master];

EXECUTE AS LOGIN = N'sa';
PRINT 'Creating databases...';
CREATE DATABASE [DatabaseA] COLLATE Latin1_General_100_CI_AS_SC;
CREATE DATABASE [DatabaseB] COLLATE Latin1_General_100_CI_AS_SC;
REVERT;
GO

-- Default for both options should be OFF, but just to be sure:
ALTER DATABASE [DatabaseA] SET DB_CHAINING OFF;
ALTER DATABASE [DatabaseA] SET TRUSTWORTHY OFF;

ALTER DATABASE [DatabaseB] SET DB_CHAINING OFF;
ALTER DATABASE [DatabaseB] SET TRUSTWORTHY OFF;
GO

CREATE LOGIN [JohnnyLunchbucket] WITH PASSWORD = 'OhSoSecure;)';


USE [DatabaseA];

CREATE USER [JohnnyLunchbucket] FOR LOGIN [JohnnyLunchbucket];
GO

--DROP PROCEDURE dbo.InsertIntoTableWithoutTrigger;
CREATE PROCEDURE dbo.InsertIntoTableWithoutTrigger
(
    @SomeValue NVARCHAR(50)
)
AS
SET NOCOUNT ON;

INSERT INTO [DatabaseB].[dbo].[TableWithoutTrigger] (SomeValue)
VALUES (@SomeValue);
GO

GRANT EXECUTE ON dbo.InsertIntoTableWithoutTrigger TO [JohnnyLunchbucket];
GO

CREATE PROCEDURE dbo.InsertIntoTableWithTrigger
AS
SET NOCOUNT ON;

INSERT INTO [DatabaseB].[dbo].[TableWithTrigger] (SomeOtherValue)
VALUES (NEWID());
GO

GRANT EXECUTE ON dbo.InsertIntoTableWithTrigger TO [JohnnyLunchbucket];



CREATE CERTIFICATE [PermissionsCert]
  AUTHORIZATION [dbo]
  ENCRYPTION BY PASSWORD = 'WeakPassword'
  WITH SUBJECT = 'Used to test granting permissions to code',
  EXPIRY_DATE = '2099-12-31';

ADD SIGNATURE TO [dbo].[InsertIntoTableWithoutTrigger]
    BY CERTIFICATE [PermissionsCert]
    WITH PASSWORD = 'WeakPassword';

ADD SIGNATURE TO [dbo].[InsertIntoTableWithTrigger]
    BY CERTIFICATE [PermissionsCert]
    WITH PASSWORD = 'WeakPassword';

-- Save Certificate info in temporary table so we can recreate in DatabaseB
SELECT CERTENCODED(CERT_ID(N'PermissionsCert')) AS [PublicKey],
       CERTPRIVATEKEY(CERT_ID(N'PermissionsCert'), 'OtherPassword', 'WeakPassword')
              AS [PrivateKey]
INTO   #CertInfo;
GO

USE [DatabaseB];

DECLARE @SQL NVARCHAR(MAX);

SELECT @SQL = N'CREATE CERTIFICATE [PermissionsCert] AUTHORIZATION [dbo] FROM BINARY = '
               + CONVERT(NVARCHAR(MAX), [PublicKey], 1)
               + N' WITH PRIVATE KEY (BINARY = '
               + CONVERT(NVARCHAR(MAX), [PrivateKey], 1)
               + N', DECRYPTION BY PASSWORD = N''OtherPassword'''
               + N', ENCRYPTION BY PASSWORD = ''WeakPassword'');'
FROM   #CertInfo;

PRINT @SQL;
EXEC (@SQL);

CREATE USER [PermissionsUser] FROM CERTIFICATE [PermissionsCert];

--DROP TABLE dbo.[TableWithoutTrigger];
CREATE TABLE dbo.[TableWithoutTrigger]
(
  [TableWithoutTriggerID] INT NOT NULL IDENTITY(1, 1)
     CONSTRAINT [PK_TableWithoutTrigger] PRIMARY KEY,
  [SomeValue] NVARCHAR(50)
);

GRANT INSERT ON [dbo].[TableWithoutTrigger] TO [PermissionsUser];


CREATE TABLE dbo.[TableWithTrigger]
(
  [TableWithTriggerID] INT NOT NULL IDENTITY(1, 1)
     CONSTRAINT [PK_TableWithTrigger] PRIMARY KEY,
  [SomeOtherValue] NVARCHAR(50)
);

GRANT INSERT ON [dbo].[TableWithTrigger] TO [PermissionsUser];


CREATE TABLE dbo.[TablePopulatedByTrigger]
(
  [TablePopulatedByTriggerID] INT NOT NULL IDENTITY(1, 1)
     CONSTRAINT [PK_TablePopulatedByTrigger] PRIMARY KEY,
  [DuplicatedValue] NVARCHAR(50)
);
GO

CREATE TRIGGER dbo.CopySomeOtherValue
ON dbo.[TableWithTrigger]
AFTER INSERT
AS
BEGIN
    SET NOCOUNT ON;

    INSERT INTO dbo.[TablePopulatedByTrigger] ([DuplicatedValue])
        SELECT ins.[SomeOtherValue]
        FROM   inserted ins;
END;
GO


TEST 1: Trigger fails

USE [DatabaseA];

EXECUTE AS LOGIN = 'JohnnyLunchbucket';
SELECT SESSION_USER AS [User], ORIGINAL_LOGIN() AS [OriginalLogin];
GO

SELECT * FROM [DatabaseB].[dbo].[TableWithoutTrigger];
SELECT * FROM [DatabaseB].[dbo].[TableWithTrigger];
SELECT * FROM [DatabaseB].[dbo].[TablePopulatedByTrigger];
INSERT INTO [DatabaseB].[dbo].[TableWithoutTrigger] ([SomeValue]) VALUES (N'test 0');
USE [DatabaseB];
/* -- All 5 statements above get the following error:
Msg 916, Level 14, State 1, Line xxxxxx
The server principal "JohnnyLunchbucket" is not able to access the database
    "DatabaseB" under the current security context.
*/


EXEC [dbo].[InsertIntoTableWithoutTrigger] @SomeValue = N'test A'; -- SUCCESS!!!

EXEC [dbo].[InsertIntoTableWithTrigger]; -- ERROR:
/*
Msg 916, Level 14, State 1, Procedure CopySomeOtherValue, Line xxxxxx
The server principal "JohnnyLunchbucket" is not able to access the database
    "DatabaseB" under the current security context.
*/

REVERT;
SELECT SESSION_USER AS [User], ORIGINAL_LOGIN() AS [OriginalLogin];

-- Check to make sure that dbo.InsertIntoTableWithoutTrigger really did work:
SELECT * FROM [DatabaseB].[dbo].[TableWithoutTrigger];
-- 1    test A


TEST 2: Trigger succeeds  

Please note that the only change being made is ADD COUNTER SIGNATURE; there is no GRANT INSERT ON dbo.TablePopulatedByTrigger TO [PermissionsUser];.

USE [DatabaseB];

ADD COUNTER SIGNATURE
    TO dbo.[CopySomeOtherValue]
    BY CERTIFICATE [PermissionsCert]
    WITH PASSWORD = 'WeakPassword';
GO


USE [DatabaseA];

EXECUTE AS LOGIN = 'JohnnyLunchbucket';
SELECT SESSION_USER AS [User], ORIGINAL_LOGIN() AS [OriginalLogin];
GO

INSERT INTO [DatabaseB].[dbo].[TableWithTrigger] ([SomeOtherValue]) VALUES (N'Test B');
INSERT INTO [DatabaseB].[dbo].[TablePopulatedByTrigger]([DuplicatedValue]) VALUES ('Test B')
/*
Msg 916, Level 14, State 1, Line xxxxxx
The server principal "JohnnyLunchbucket" is not able to access the database
    "DatabaseB" under the current security context.
*/


EXEC [dbo].[InsertIntoTableWithTrigger]; -- SUCCESS!!!

REVERT;
SELECT SESSION_USER AS [User], ORIGINAL_LOGIN() AS [OriginalLogin];

SELECT * FROM [DatabaseB].[dbo].[TableWithTrigger];
SELECT * FROM [DatabaseB].[dbo].[TablePopulatedByTrigger];
-- 2    968DB092-C3DE-4E4B-92B9-E21CA551A5FA
-- 1    968DB092-C3DE-4E4B-92B9-E21CA551A5FA