After a workflow started, the notifications are not arriving to users inbox.

Hi all,

IN PUBLISH ENVIRONMENT.
We are having several problems with a workflow where we have a step where administrators have to approve it manually from their inbox.
We have a registration process where the user selects a Role. If the Role selected is B, then a workflow starts and it (should) send a notification to the administrators group with this approvement request.
The weird thing here is that sometimes the notification arrive and sometimes it is not. I tried registering 5 users. User1, User2, User3, User4 and User5, in that order. When I check the inbox I see notifications for: User1, User2, User3 and User5 (No notification for User4 :( ). After that I registered 4 more users, but sadly no more notifications arrived.
I spent hours looking at the Log File. I found things like these after the registration of User4:

21.01.2015 11:13:29.579 *INFO* [pool-6-thread-5-com_day_cq_replication_job_outbox(com/day/cq/replication/job/outbox)] com.day.cq.replication.Agent.outbox.queue Job for agent outbox processed in 17ms. Ok.
.
.
.

21.01.2015 11:14:08.663 *WARN* [181.228.37.208 [1421856848634] GET /libs/cq/workflow/content/inbox/list.json HTTP/1.1] com.adobe.granite.workflow.core.PayloadMapCache Unable to get workflow instance: Unable to retrieve workflow instance: /etc/workflow/instances/2015-01-21/model_83350194040380 (A LOT of these warnings)

I wish someone could help us with this soon. I ran out of ideas here :(

Thanks in advance.

Clemente.