Ciao, perchè è da un pò che lo store non mi segnala più gli aggiornamenti? (sia su tile sia nello store).
Come posso risolvere?

C'è un bug nelle notifiche di Windows Phone...

Prova questo metodo:
1. Togli la tile dal menu start
2. fai un soft reset del telefono (dovrebbe essere volume - e tasto di spegnimento per 10 secondi, se mi dai il modello del telefono, ti posso dare una risposta certa, comunque non perdi alcun dato)
3. aggiungi nuovamente la tile sullo start
4. Tieni connesso il telefono per 24h (provaci).
La tile dovrebbe aggiornarsi.
Consiglio di provare la procedura in un orario in cui il telefono è connesso a internet

E' un Lumia 920. Cosa intendi per connesso? Connesso via WI-FI o 3G? Perchè il cell è sempre connesso ad internet con il 3G mentre da metà giornata è connesso tramite Wi-Fi.

Intende a internet se non sbaglio

SI, parlo di connessione dati (3G o wifi), però dovresti provare dopo il soft-reset (ti posso confermare volume giù + tasto spegnimento, per una doppia verifica, controlla sul manuale del telefono)

Però io la tile é da un paio di giorni che l'ho rimossa dalla start-screen; il soft reset mi risolverà lo stesso il problema? O dopo il SR devo mettere per forza la tile sulla start-screen?

Io ho provato questo metodo tempo fa ed ha funzionato e funziona tutto ora.
Col soft reset non perdi nulla, é un po come spegnere e riaccendere il telefono, perdi solo l'orario se non erro. Prima di farlo ( come dici hai già fatto ), togliere la tile dallo start