Maybe you have another web alias on the domain, besides the default www ?
If you have another alias (e.g. super.mydomain.com) then you need to have an A record “super” to point to the server’s IP (like the www one). If you have more aliases, then you need an A record for each one of them.