I'm not a native speaker or a great speaker at that, but I've always heard 海边 and not 海旁边. Perhaps 海旁边 is grammatically correct but just shortened to 海边? I think this is a good question, and would be interested in an answer too, if anyone knows it.