What I'd suggest is, instead of sending the mail direct from a trigger (which is usually a bad idea anyway), have the trigger write the info for the mails into another table (call it PendingEmails or something) and have a job that runs regularly that checks that, iterates through any rows and sends any mails.

So then the trigger would just looks like this

IF UPDATE (city)

insert into PendingEmails (UserID, OldCity, NewCity)

SELECT i.userid, d.city, i.city FROM inserted inner join deleted ON ... (put the appropriate join based on the PK of the table)

WHERE i,city != d,city -- don't catch cases where the city has been updated to the same value

AND d.city LIKE 'p% or d.city LIKE 's%'

Edit: columns wrong way around.