Well there should be nothing wrong with virginmedia or gmail addresses used anywhere. The issue must be with how you are submitting them on your device, particularly if it is intermittent.
Definitely don't use copy / paste since it is easy to pick up spurious spaces or other control characters which might not be visible to your eye. Always type them out manually and carefully. Another thing to watch for is autocorrect. Make sure the device is not changing what you are putting in without you noticing it.
Also, ensure you are always picking up and entering any validation fields on the site - i.e. where they ask you to repeat your address to validate you typed it correctly. The number of times I've seen folks misunderstand or ignore those and subsequently spent hours trying to help them is incredible!
The bottom line is sites like the ones you mention (John Lewis etc.) and email providers like gmail etc. do not have any kind of widespread problems with their infrastructure. The deal with these types of transactions millions of times a day. It is much more likely, given you are working with completely normal email addresses, that the issue is at your end, and no offence intended, but in my experience 99% of the time it's the human to blame...
Hope you get it sorted.
