Eamorr,
O operador $pull não funcionará no documento que você está usando, porque a chave "notificações" não é realmente uma matriz. É mais um documento embutido, com chaves numeradas, tornando-o superficialmente parecido com um array. Não há nenhuma maneira (que eu saiba) de manter essa estrutura de documento e ter as chaves numeradas renomeadas automaticamente.
Se você refatorar um pouco seu documento, para ficar assim:
{
"notifications": [
{
"type": "privateMessage",
"fromUname": "Eamorr2",
"time": 1292773522,
"id": "1lfw70h789u13a1e67pv"
},
{
"type": "privateMessage",
"fromUname": "Eamorr2",
"time": 1292773522,
"id": "iwoidjsoskqp23nlwof"
}
],
"toUname": "Eamorr"
}
Os elementos ainda serão numerados, implicitamente. Agora é um array, então você obtém isso de graça. Você pode usar o operador $pull assim (não estou familiarizado com o driver PHP, então estou dando a você o equivalente do shell):
db.messages.update({ "toUname" : "Eamorr" }, { $pull : { "notifications" : { "id" : "1lfw70h789u13a1e67pv" }}});
Eu usei arbitrariamente a chave "toUname" para identificar o documento, mas acho que você vai querer usar o campo _id. Além disso, estou usando a chave "id" das mensagens para identificar a mensagem a ser extraída do array, pois é muito mais seguro e garante que você não remova acidentalmente a mensagem errada caso o array tenha mudado desde você identificou o ordinal da matriz a ser removido.
Espero que isso ajude.