Mining sequential patterns from temporal transaction databases attempts to find customer behavior models and to assist managers in making correct and effective decisions. The sequential patterns discovered may, however, become invalid or inappropriate when databases are updated. Conventional approaches may re-mine entire databases to get correct sequential patterns for maintenance. However, when a database is massive in size, this will require considerable computation time. In the past, Lin and Lee proposed an incremental mining algorithm for maintenance of sequential patterns as new records were inserted. In addition to record insertion, record deletion is also commonly seen in real-world applications. Processing record deletion is, however, different from processing record insertion. The former can even be thought of the contrary of the latter. In this paper, we thus attempt to design an effective maintenance algorithm for sequential patterns as records are deleted. Our proposed algorithm utilizes previously discovered large sequences in the maintenance process, thus reducing numbers of rescanning databases. In addition, rescanning requirement depends on decreased numbers of customers, which are usually zero when numbers of deleted records are not large. This characteristic is especially useful for dynamic database mining.