Timing attacks like you mention here are trivially easy to prevent.

Step 1: Determine how long a query for a not found user may take... Let's say 1-2 seconds since there may be many rows to deal with.

Step 2: Multiply the value in step 1 by two or at least add a comfortable margin, perhaps 5 seconds total.

Step 3: On the start of the request performing the look up spawn a separate timing thread.

Step 4: At the end of the request join the timing thread.

This will tie the processing time of the request to the uniform time out value instead of your database processing delay.