Availability Group database stuck in Initializing / In Recovery mode even after restarting service
Well, when I saw the error messages I figured the database was not added to the Availability group, but after checking the Availability Databases in SSMS on the new replica it was there with a pause symbol next to it. This means it was added but the data movement has stopped. I tried resuming data movement, but it was too far behind. So instead I had to remove it from the availability group and manually apply log files so it could start replicating again.

-- Remove database from Availability Group:    
Alter Database [StackExchange.Aviation.Meta] SET HADR OFF;

-- Apply t-logs to catch up. This can be done manually in SSMS or via:
RESTORE LOG [StackExchange.Aviation.Meta] FROM DISK = '\\Backups\SQL\_Trans\StackExchange.Aviation.Meta_LOG_20170901_043251.trn' WITH NORECOVERY;

-- Re-join database to availability group
ALTER DATABASE [StackExchange.Aviation.Meta] SET HADR AVAILABILITY GROUP = [SENetwork_RAG];
ALTER DATABASE [StackExchange.Aviation.Meta] SET HADR RESUME;


I should have noticed it was added, but the AG has over 300 DBs and was still in the process of seeding so it was missed among the noise. The "Lock request time out" error message also made me think that something had gone wrong in the seeding, but it was just a poorly worded message indicating the database was already part of the Availability Group.