Can send test database mail but job emails failing
When you use Send Test Email, SSMS is using your credentials. When SQL Agent attempts to connect to the mail profile, it's using the SQL Agent service account credentials. That would be a major difference, and it wouldn't have anything to do with time of day...just credentials.
You can test it by scheduling a job that has a task that will fail (i.e. Select * from northwind) and let the SQL Agent run it, and find out if it will send the notification. That will at least eliminate the service account permission possibility...