I have enabled cookies - why are sites saying I haven't?

I have IE 5.5 and I swear, promise and assure that have enabled cookies under Internet Options>Security on my browser. I’ve checked a dozen times. However, sites requiring cookies to be enabled are still claiming I haven’t done so. Examples include expedia.co.uk.

Also - and I assume this is related since it started happening at the same time - my browser is not automatically forwarding me when it should. For example, when posting here I am stuck on the “thank you for posting” screen and go no further. The same happens with hotmail - I get stuck between the login screen and my inbox.

Can anyone tell me why this is happening and what I can do to solve it? Thanks in advance.