How to avoid MySQL 'Deadlock found when trying to get lock; try restarting transaction'

I have a innoDB table which records online users. It gets updated on every page refresh by a user to keep track of which pages they are on and their last access date to the site. I then have a cron that runs every 15 minutes to DELETE old records. I got a 'Deadlock found when trying to get lock; try restarting transaction' for about 5 minutes last night and it appears to be when running INSERTs into this table. Can someone suggest how to avoid this error? === EDIT === Here are the queries that are running: **First Visit to site:** INSERT INTO onlineusers SET ip = 123.456.789.123, datetime = now(), userid = 321, page = '/thispage', area = 'thisarea', type = 3 **On each page refresh:** UPDATE onlineusers SET ips = 123.456.789.123, datetime = now(), userid = 321, page = '/thispage', area = 'thisarea', type = 3 WHERE id = 888 **Cron every 15 minutes:** DELETE FROM onlineusers WHERE datetime <= now() - INTERVAL 900 SECOND It then does some counts to log some stats (ie: members online, visitors online).