The ordered data structure you're dreaming of is an array. It is an ordered sequence and there is an example of it in the data structure created when parsing either YAML format of the data in question. If you want to create an ordered sequence in the YAML output, use a Perl array.

From YAML spec 1.2:

# Ordered maps are represented as
# A sequence of mappings, with
# each mapping having one key
--- !!omap
- Mark McGwire: 65
- Sammy Sosa: 63
- Ken Griffy: 58
[download]

Which produces this Perl data structure

[
  { "Mark McGwire" => 65 },
  { "Sammy Sosa" => 63 },
  { "Ken Griffy" => 58 },
]
[download]

So lets duplicate that with your data

[
  { path => "/export/home/frank" },
  {
    options => [
      { param => "i", value => 1001 },
      { param => "f" },
      { param => "x", value => "eyes" },
      {},
      { param => "b", value => "toes" },
      { param => "p" },
    ],
  },
  { arguments => [{ value => "test" }] },
]
[download]

Which produces the format suggested by the YAML spec:

---
- path: /export/home/frank
- options:
  - param: i
    value: '1001'
  - param: f
  - param: x
    value: eyes
  - {}
  - param: b
    value: toes
  - param: p
- arguments:
  - value: test
[download]

So we see how to create ordered mappings in both YAML and in Perl. YAML::XS is doing exactly the right thing because Perl hashes are not ordered, therefore it outputs them as unordered mappings. So the real question is which Perl data structure you're going to use to represent Ordered Mappings, because Perl hashes can't do that job and arrays of individual hashes aren't convenient.

Several people have suggested Tie::IxHash and this is a very good choice. But since YAML::XS sees it as just a regular hash, it outputs in unordered YAML notation. You will have to preprocess your data structures to convert IxHash's into arrays of individual mappings and reverse the process when loading.