Is it valid to replace http:// with // in a <script src="http://...">?

It is guaranteed to work in any mainstream browser (I'm not taking browsers with less than 0.05% market share into consideration). Heck, it works in Internet Explorer 3.0.

RFC 3986 defines a URI as composed of the following parts:

     foo://example.com:8042/over/there?name=ferret#nose
     \_/   \______________/\_________/ \_________/ \__/
      |           |            |            |        |
   scheme     authority       path        query   fragment

When defining relative URIs (Section 5.2), you can omit any of those sections, always starting from the left. In pseudo-code, it looks like this:

 result = ""

  if defined(scheme) then
     append scheme to result;
     append ":" to result;
  endif;

  if defined(authority) then
     append "//" to result;
     append authority to result;
  endif;

  append path to result;

  if defined(query) then
     append "?" to result;
     append query to result;
  endif;

  if defined(fragment) then
     append "#" to result;
     append fragment to result;
  endif;

  return result;

The URI you are describing is a scheme-less relative URI.

A relative URL without a scheme (http: or https:) is valid, per RFC 3986: "Uniform Resource Identifier (URI): Generic Syntax", Section 4.2. If a client chokes on it, then it's the client's fault because they're not complying with the URI syntax specified in the RFC.

Your example is valid and should work. I've used that relative URL method myself on heavily trafficked sites and have had zero complaints. Also, we test our sites in Firefox, Safari, IE6, IE7 and Opera. These browsers all understand that URL format.

are there any cases where it doesn't work?

If the parent page was loaded from file://, then it probably does not work (it will try to get file://cdn.example.com/js_file.js, which of course you could provide locally as well).