Windows XP search

The search feature olny works if you are connected to the Internet. The many tips and tricks from Microsoft do not solve the problem. This happens on all the new Dell PCs we are installing that came with Windows XP. Dell has no clue. Is this a known problem?