diff --git a/keyserver/src/push/crypto.js b/keyserver/src/push/crypto.js
--- a/keyserver/src/push/crypto.js
+++ b/keyserver/src/push/crypto.js
@@ -2,17 +2,21 @@
 
 import apn from '@parse/node-apn';
 import invariant from 'invariant';
+import _cloneDeep from 'lodash/fp/cloneDeep.js';
 
 import type {
   AndroidNotification,
+  AndroidNotificationPayload,
   AndroidNotificationRescind,
+  NotificationTargetDevice,
 } from './types.js';
 import { encryptAndUpdateOlmSession } from '../updaters/olm-session-updater.js';
 
 async function encryptIOSNotification(
   cookieID: string,
   notification: apn.Notification,
-): Promise<apn.Notification> {
+  notificationSizeValidator?: apn.Notification => boolean,
+): Promise<{ +notification: apn.Notification, +payloadSizeExceeded: boolean }> {
   invariant(
     !notification.collapseId,
     'Collapsible notifications encryption currently not implemented',
@@ -34,15 +38,34 @@
     merged: notification.body,
   };
 
-  let encryptedSerializedPayload;
   try {
     const unencryptedSerializedPayload = JSON.stringify(unencryptedPayload);
+
+    let dbPersistCondition;
+    if (notificationSizeValidator) {
+      dbPersistCondition = ({ serializedPayload }) => {
+        const notifCopy = _cloneDeep(encryptedNotification);
+        notifCopy.payload.encryptedPayload = serializedPayload.body;
+        return notificationSizeValidator(notifCopy);
+      };
+    }
     const {
       encryptedMessages: { serializedPayload },
-    } = await encryptAndUpdateOlmSession(cookieID, 'notifications', {
-      serializedPayload: unencryptedSerializedPayload,
-    });
-    encryptedSerializedPayload = serializedPayload;
+      dbPersistConditionViolated,
+    } = await encryptAndUpdateOlmSession(
+      cookieID,
+      'notifications',
+      {
+        serializedPayload: unencryptedSerializedPayload,
+      },
+      dbPersistCondition,
+    );
+
+    encryptedNotification.payload.encryptedPayload = serializedPayload.body;
+    return {
+      notification: encryptedNotification,
+      payloadSizeExceeded: !!dbPersistConditionViolated,
+    };
   } catch (e) {
     console.log('Notification encryption failed: ' + e);
 
@@ -59,53 +82,102 @@
       ...notification.payload,
       encryptionFailed: 1,
     };
-    return encryptedNotification;
+    return {
+      notification: encryptedNotification,
+      payloadSizeExceeded: notificationSizeValidator
+        ? notificationSizeValidator(_cloneDeep(encryptedNotification))
+        : false,
+    };
   }
-
-  encryptedNotification.payload.encryptedPayload =
-    encryptedSerializedPayload.body;
-  return encryptedNotification;
 }
 
 async function encryptAndroidNotificationPayload<T>(
   cookieID: string,
   unencryptedPayload: T,
-): Promise<T | { +encryptedPayload: string }> {
+  payloadSizeValidator?: (T | { +encryptedPayload: string }) => boolean,
+): Promise<{
+  +resultPayload: T | { +encryptedPayload: string },
+  +payloadSizeExceeded: boolean,
+}> {
   try {
     const unencryptedSerializedPayload = JSON.stringify(unencryptedPayload);
     if (!unencryptedSerializedPayload) {
-      return unencryptedPayload;
+      return {
+        resultPayload: unencryptedPayload,
+        payloadSizeExceeded: payloadSizeValidator
+          ? payloadSizeValidator(unencryptedPayload)
+          : false,
+      };
+    }
+
+    let dbPersistCondition;
+    if (payloadSizeValidator) {
+      dbPersistCondition = ({ serializedPayload }) =>
+        payloadSizeValidator({ encryptedPayload: serializedPayload.body });
     }
+
     const {
       encryptedMessages: { serializedPayload },
-    } = await encryptAndUpdateOlmSession(cookieID, 'notifications', {
-      serializedPayload: unencryptedSerializedPayload,
-    });
-    return { encryptedPayload: serializedPayload.body };
+      dbPersistConditionViolated,
+    } = await encryptAndUpdateOlmSession(
+      cookieID,
+      'notifications',
+      {
+        serializedPayload: unencryptedSerializedPayload,
+      },
+      dbPersistCondition,
+    );
+    return {
+      resultPayload: { encryptedPayload: serializedPayload.body },
+      payloadSizeExceeded: !!dbPersistConditionViolated,
+    };
   } catch (e) {
     console.log('Notification encryption failed: ' + e);
-    return {
+    const resultPayload = {
       encryptionFailed: '1',
       ...unencryptedPayload,
     };
+    return {
+      resultPayload,
+      payloadSizeExceeded: payloadSizeValidator
+        ? payloadSizeValidator(resultPayload)
+        : false,
+    };
   }
 }
 
 async function encryptAndroidNotification(
   cookieID: string,
   notification: AndroidNotification,
-): Promise<AndroidNotification> {
+  notificationSizeValidator?: AndroidNotification => boolean,
+): Promise<{
+  +notification: AndroidNotification,
+  +payloadSizeExceeded: boolean,
+}> {
   const { id, badgeOnly, ...unencryptedPayload } = notification.data;
-  const encryptedSerializedPayload = await encryptAndroidNotificationPayload(
-    cookieID,
-    unencryptedPayload,
-  );
+  let payloadSizeValidator;
+  if (notificationSizeValidator) {
+    payloadSizeValidator = (
+      payload: AndroidNotificationPayload | { +encryptedPayload: string },
+    ) => {
+      return notificationSizeValidator({ data: { id, badgeOnly, ...payload } });
+    };
+  }
+  const { resultPayload, payloadSizeExceeded } =
+    await encryptAndroidNotificationPayload(
+      cookieID,
+      unencryptedPayload,
+      payloadSizeValidator,
+    );
   return {
-    data: {
-      id,
-      badgeOnly,
-      ...encryptedSerializedPayload,
+    notification: {
+      data: {
+        id,
+        badgeOnly,
+        ...resultPayload,
+      },
     },
+    payloadSizeExceeded,
   };
 }
 
@@ -113,47 +185,115 @@
   cookieID: string,
   notification: AndroidNotificationRescind,
 ): Promise<AndroidNotificationRescind> {
-  const encryptedPayload = await encryptAndroidNotificationPayload(
+  // We don't validate payload size for rescind
+  // since they are expected to be small and
+  // never exceed any FCM limit
+  const { resultPayload } = await encryptAndroidNotificationPayload(
     cookieID,
     notification.data,
   );
   return {
-    data: encryptedPayload,
+    data: resultPayload,
   };
 }
 
 function prepareEncryptedIOSNotifications(
-  cookieIDs: $ReadOnlyArray<string>,
+  devices: $ReadOnlyArray<NotificationTargetDevice>,
+  notification: apn.Notification,
+  notificationSizeValidator?: apn.Notification => boolean,
+): Promise<
+  $ReadOnlyArray<{
+    +cookieID: string,
+    +deviceToken: string,
+    +notification: apn.Notification,
+    +payloadSizeExceeded: boolean,
+  }>,
+> {
+  const notificationPromises = devices.map(
+    async ({ cookieID, deviceToken }) => {
+      const notif = await encryptIOSNotification(
+        cookieID,
+        notification,
+        notificationSizeValidator,
+      );
+      return { cookieID, deviceToken, ...notif };
+    },
+  );
+  return Promise.all(notificationPromises);
+}
+
+function prepareEncryptedIOSNotificationRescind(
+  devices: $ReadOnlyArray<NotificationTargetDevice>,
   notification: apn.Notification,
-): Promise<$ReadOnlyArray<apn.Notification>> {
-  const notificationPromises = cookieIDs.map(cookieID =>
-    encryptIOSNotification(cookieID, notification),
+): Promise<
+  $ReadOnlyArray<{
+    +cookieID: string,
+    +deviceToken: string,
+    +notification: apn.Notification,
+  }>,
+> {
+  const notificationPromises = devices.map(
+    async ({ deviceToken, cookieID }) => {
+      const { notification: notif } = await encryptIOSNotification(
+        cookieID,
+        notification,
+      );
+      return { deviceToken, cookieID, notification: notif };
+    },
   );
   return Promise.all(notificationPromises);
 }
 
 function prepareEncryptedAndroidNotifications(
-  cookieIDs: $ReadOnlyArray<string>,
+  devices: $ReadOnlyArray<NotificationTargetDevice>,
   notification: AndroidNotification,
-): Promise<$ReadOnlyArray<AndroidNotification>> {
-  const notificationPromises = cookieIDs.map(cookieID =>
-    encryptAndroidNotification(cookieID, notification),
+  notificationSizeValidator?: (notification: AndroidNotification) => boolean,
+): Promise<
+  $ReadOnlyArray<{
+    +cookieID: string,
+    +deviceToken: string,
+    +notification: AndroidNotification,
+    +payloadSizeExceeded: boolean,
+  }>,
+> {
+  const notificationPromises = devices.map(
+    async ({ deviceToken, cookieID }) => {
+      const notif = await encryptAndroidNotification(
+        cookieID,
+        notification,
+        notificationSizeValidator,
+      );
+      return { deviceToken, cookieID, ...notif };
+    },
   );
   return Promise.all(notificationPromises);
 }
 
 function prepareEncryptedAndroidNotificationRescinds(
-  cookieIDs: $ReadOnlyArray<string>,
+  devices: $ReadOnlyArray<NotificationTargetDevice>,
   notification: AndroidNotificationRescind,
-): Promise<$ReadOnlyArray<AndroidNotificationRescind>> {
-  const notificationPromises = cookieIDs.map(cookieID =>
-    encryptAndroidNotificationRescind(cookieID, notification),
+): Promise<
+  $ReadOnlyArray<{
+    +cookieID: string,
+    +deviceToken: string,
+    +notification: AndroidNotificationRescind,
+  }>,
+> {
+  const notificationPromises = devices.map(
+    async ({ deviceToken, cookieID }) => {
+      const notif = await encryptAndroidNotificationRescind(
+        cookieID,
+        notification,
+      );
+      return { deviceToken, cookieID, notification: notif };
+    },
   );
   return Promise.all(notificationPromises);
 }
 
 export {
   prepareEncryptedIOSNotifications,
+  prepareEncryptedIOSNotificationRescind,
   prepareEncryptedAndroidNotifications,
   prepareEncryptedAndroidNotificationRescinds,
 };
diff --git a/keyserver/src/push/rescind.js b/keyserver/src/push/rescind.js
--- a/keyserver/src/push/rescind.js
+++ b/keyserver/src/push/rescind.js
@@ -9,7 +9,7 @@
 
 import {
   prepareEncryptedAndroidNotificationRescinds,
-  prepareEncryptedIOSNotifications,
+  prepareEncryptedIOSNotificationRescind,
 } from './crypto.js';
 import { getAPNsNotificationTopic } from './providers.js';
 import type {
@@ -226,9 +226,15 @@
   codeVersion: ?number,
   devices: $ReadOnlyArray<NotificationTargetDevice>,
   encryptCallback: (
-    cookieIDs: $ReadOnlyArray<string>,
+    devices: $ReadOnlyArray<NotificationTargetDevice>,
     notification: T,
-  ) => Promise<$ReadOnlyArray<T>>,
+  ) => Promise<
+    $ReadOnlyArray<{
+      +notification: T,
+      +cookieID: string,
+      +deviceToken: string,
+    }>,
+  >,
 ): Promise<$ReadOnlyArray<{ +deviceToken: string, +notification: T }>> {
   const shouldBeEncrypted = codeVersion && codeVersion >= 233;
   if (!shouldBeEncrypted) {
@@ -237,16 +243,11 @@
       deviceToken,
     }));
   }
-  const notificationPromises = devices.map(({ cookieID, deviceToken }) =>
-    (async () => {
-      const [encryptedNotif] = await encryptCallback([cookieID], notification);
-      return {
-        notification: encryptedNotif,
-        deviceToken,
-      };
-    })(),
-  );
-  return await Promise.all(notificationPromises);
+  const notifications = await encryptCallback(devices, notification);
+  return notifications.map(({ deviceToken, notification: notif }) => ({
+    deviceToken,
+    notification: notif,
+  }));
 }
 
 async function prepareIOSNotification(
@@ -289,7 +290,7 @@
     notification,
     codeVersion,
     devices,
-    prepareEncryptedIOSNotifications,
+    prepareEncryptedIOSNotificationRescind,
   );
 }
 
diff --git a/keyserver/src/push/send.js b/keyserver/src/push/send.js
--- a/keyserver/src/push/send.js
+++ b/keyserver/src/push/send.js
@@ -662,8 +662,13 @@
   const isTextNotification = newRawMessageInfos.every(
     newRawMessageInfo => newRawMessageInfo.type === messageTypes.TEXT,
   );
+
   const shouldBeEncrypted =
-    platformDetails.platform === 'ios' && !collapseKey && isTextNotification;
+    platformDetails.platform === 'ios' &&
+    !collapseKey &&
+    isTextNotification &&
+    platformDetails.codeVersion &&
+    platformDetails.codeVersion > 222;
 
   const uniqueID = uuidv4();
   const notification = new apn.Notification();
@@ -706,40 +711,63 @@
     messageInfos,
   };
 
-  const evaluateAndSelectNotifPayload = (notif, notifWithMessageInfos) => {
-    const notifWithMessageInfosCopy = _cloneDeep(notifWithMessageInfos);
-    if (
-      notifWithMessageInfosCopy.length() <= apnMaxNotificationPayloadByteSize
-    ) {
-      return notifWithMessageInfos;
-    }
-    return notif;
-  };
-
-  const deviceTokens = devices.map(({ deviceToken }) => deviceToken);
-  if (
-    shouldBeEncrypted &&
-    platformDetails.codeVersion &&
-    platformDetails.codeVersion > 222
-  ) {
-    const cookieIDs = devices.map(({ cookieID }) => cookieID);
-    const [notifications, notificationsWithMessageInfos] = await Promise.all([
-      prepareEncryptedIOSNotifications(cookieIDs, notification),
-      prepareEncryptedIOSNotifications(cookieIDs, copyWithMessageInfos),
-    ]);
-    return notificationsWithMessageInfos.map((notif, idx) => ({
-      notification: evaluateAndSelectNotifPayload(notifications[idx], notif),
-      deviceToken: deviceTokens[idx],
+  const notificationSizeValidator = notif =>
+    notif.length() <= apnMaxNotificationPayloadByteSize;
+
+  if (!shouldBeEncrypted) {
+    const notificationToSend = notificationSizeValidator(
+      _cloneDeep(copyWithMessageInfos),
+    )
+      ? copyWithMessageInfos
+      : notification;
+    return devices.map(({ deviceToken }) => ({
+      notification: notificationToSend,
+      deviceToken,
     }));
   }
-  const notificationToSend = evaluateAndSelectNotifPayload(
-    notification,
+
+  const notifsWithMessageInfos = await prepareEncryptedIOSNotifications(
+    devices,
     copyWithMessageInfos,
+    notificationSizeValidator,
   );
-  return deviceTokens.map(deviceToken => ({
-    notification: notificationToSend,
-    deviceToken,
-  }));
+
+  const devicesWithExcessiveSize = notifsWithMessageInfos
+    .filter(({ payloadSizeExceeded }) => payloadSizeExceeded)
+    .map(({ deviceToken, cookieID }) => ({ deviceToken, cookieID }));
+
+  if (devicesWithExcessiveSize.length === 0) {
+    return notifsWithMessageInfos.map(
+      ({ notification: notif, deviceToken }) => ({
+        notification: notif,
+        deviceToken,
+      }),
+    );
+  }
+
+  const notifsWithoutMessageInfos = await prepareEncryptedIOSNotifications(
+    devicesWithExcessiveSize,
+    notification,
+  );
+
+  const targetedNotifsWithMessageInfos = notifsWithMessageInfos
+    .filter(({ payloadSizeExceeded }) => !payloadSizeExceeded)
+    .map(({ notification: notif, deviceToken }) => ({
+      notification: notif,
+      deviceToken,
+    }));
+
+  const targetedNotifsWithoutMessageInfos = notifsWithoutMessageInfos.map(
+    ({ notification: notif, deviceToken }) => ({
+      notification: notif,
+      deviceToken,
+    }),
+  );
+
+  return [
+    ...targetedNotifsWithMessageInfos,
+    ...targetedNotifsWithoutMessageInfos,
+  ];
 }
 
 type AndroidNotifInputData = {
@@ -807,36 +835,69 @@
     data: { ...notification.data, messageInfos },
   };
 
-  const evaluateAndSelectNotification = (notif, notifWithMessageInfos) => {
-    if (
-      Buffer.byteLength(JSON.stringify(notifWithMessageInfos)) <=
+  if (!shouldBeEncrypted) {
+    const notificationToSend =
+      Buffer.byteLength(JSON.stringify(copyWithMessageInfos)) <=
       fcmMaxNotificationPayloadByteSize
-    ) {
-      return notifWithMessageInfos;
-    }
-    return notif;
-  };
+        ? copyWithMessageInfos
+        : notification;
 
-  const deviceTokens = devices.map(({ deviceToken }) => deviceToken);
-  if (shouldBeEncrypted) {
-    const cookieIDs = devices.map(({ cookieID }) => cookieID);
-    const [notifications, notificationsWithMessageInfos] = await Promise.all([
-      prepareEncryptedAndroidNotifications(cookieIDs, notification),
-      prepareEncryptedAndroidNotifications(cookieIDs, copyWithMessageInfos),
-    ]);
-    return notificationsWithMessageInfos.map((notif, idx) => ({
-      notification: evaluateAndSelectNotification(notifications[idx], notif),
-      deviceToken: deviceTokens[idx],
+    return devices.map(({ deviceToken }) => ({
+      notification: notificationToSend,
+      deviceToken,
     }));
   }
-  const notificationToSend = evaluateAndSelectNotification(
-    notification,
+
+  const notificationsSizeValidator = notif => {
+    const serializedNotif = JSON.stringify(notif);
+    return (
+      !serializedNotif ||
+      Buffer.byteLength(serializedNotif) <= fcmMaxNotificationPayloadByteSize
+    );
+  };
+
+  const notifsWithMessageInfos = await prepareEncryptedAndroidNotifications(
+    devices,
     copyWithMessageInfos,
+    notificationsSizeValidator,
   );
-  return deviceTokens.map(deviceToken => ({
-    notification: notificationToSend,
-    deviceToken,
-  }));
+
+  const devicesWithExcessiveSize = notifsWithMessageInfos
+    .filter(({ payloadSizeExceeded }) => payloadSizeExceeded)
+    .map(({ cookieID, deviceToken }) => ({ cookieID, deviceToken }));
+
+  if (devicesWithExcessiveSize.length === 0) {
+    return notifsWithMessageInfos.map(
+      ({ notification: notif, deviceToken }) => ({
+        notification: notif,
+        deviceToken,
+      }),
+    );
+  }
+
+  const notifsWithoutMessageInfos = await prepareEncryptedAndroidNotifications(
+    devicesWithExcessiveSize,
+    notification,
+  );
+
+  const targetedNotifsWithMessageInfos = notifsWithMessageInfos
+    .filter(({ payloadSizeExceeded }) => !payloadSizeExceeded)
+    .map(({ notification: notif, deviceToken }) => ({
+      notification: notif,
+      deviceToken,
+    }));
+
+  const targetedNotifsWithoutMessageInfos = notifsWithoutMessageInfos.map(
+    ({ notification: notif, deviceToken }) => ({
+      notification: notif,
+      deviceToken,
+    }),
+  );
+
+  return [
+    ...targetedNotifsWithMessageInfos,
+    ...targetedNotifsWithoutMessageInfos,
+  ];
 }
 
 type WebNotifInputData = {
@@ -1218,22 +1279,24 @@
       notification.badge = unreadCount;
       notification.pushType = 'alert';
       const deliveryPromise = (async () => {
-        const cookieIDs = deviceInfos.map(({ cookieID }) => cookieID);
-        let notificationsArray;
+        let targetedNotifications;
         if (codeVersion > 222) {
-          notificationsArray = await prepareEncryptedIOSNotifications(
-            cookieIDs,
+          const notificationsArray = await prepareEncryptedIOSNotifications(
+            deviceInfos,
             notification,
           );
+          targetedNotifications = notificationsArray.map(
+            ({ notification: notif, deviceToken }) => ({
+              notification: notif,
+              deviceToken,
+            }),
+          );
         } else {
-          notificationsArray = cookieIDs.map(() => notification);
-        }
-        const targetedNotifications = deviceInfos.map(
-          ({ deviceToken }, idx) => ({
+          targetedNotifications = deviceInfos.map(({ deviceToken }) => ({
+            notification,
             deviceToken,
-            notification: notificationsArray[idx],
-          }),
-        );
+          }));
+        }
         return await sendAPNsNotification('ios', targetedNotifications, {
           source,
           dbID,
@@ -1255,22 +1318,24 @@
           : { badge: unreadCount.toString(), badgeOnly: '1' };
       const notification = { data: notificationData };
       const deliveryPromise = (async () => {
-        const cookieIDs = deviceInfos.map(({ cookieID }) => cookieID);
-        let notificationsArray;
+        let targetedNotifications;
         if (codeVersion > 222) {
-          notificationsArray = await prepareEncryptedAndroidNotifications(
-            cookieIDs,
+          const notificationsArray = await prepareEncryptedAndroidNotifications(
+            deviceInfos,
             notification,
           );
+          targetedNotifications = notificationsArray.map(
+            ({ notification: notif, deviceToken }) => ({
+              notification: notif,
+              deviceToken,
+            }),
+          );
         } else {
-          notificationsArray = cookieIDs.map(() => notification);
-        }
-        const targetedNotifications = deviceInfos.map(
-          ({ deviceToken }, idx) => ({
+          targetedNotifications = deviceInfos.map(({ deviceToken }) => ({
             deviceToken,
-            notification: notificationsArray[idx],
-          }),
-        );
+            notification,
+          }));
+        }
         return await sendAndroidNotification(targetedNotifications, {
           source,
           dbID,
diff --git a/keyserver/src/push/types.js b/keyserver/src/push/types.js
--- a/keyserver/src/push/types.js
+++ b/keyserver/src/push/types.js
@@ -7,16 +7,26 @@
   +deviceToken: string,
 };
 
-type AndroidNotificationPayload = {
+type AndroidNotificationPayloadBase = {
   +badge: string,
   +body?: string,
   +title?: string,
   +prefix?: string,
   +threadID?: string,
-  +messageInfos?: string,
   +encryptionFailed?: '1',
 };
 
+export type AndroidNotificationPayload =
+  | {
+      ...AndroidNotificationPayloadBase,
+      +messageInfos?: string,
+    }
+  | {
+      ...AndroidNotificationPayloadBase,
+      +blobHash: string,
+      +encryptionKey: string,
+    };
+
 export type AndroidNotification = {
   +data: {
     +id?: string,