Paginator fix still doesn't handle all cases from before
https://github.com/boto/botocore/pull/849 requires that the starting token matches the length of the input tokens, which means all input tokens need to be specified.  While this was the case for any token that came back from a botocore response, it's not the case for customers that are handcrafting starting tokens that have semantic value.  For example, here's differing behaviors on two CLI versions:

v1.9.0

```
$ aws route53 list-resource-record-sets --hosted-zone-id $ZONE_ID \\
    --max-items 1 --starting-token 'my.domain.name.' --debug
{
    "NextToken": "None___None___None___1",
    "ResourceRecordSets": [
        {
            "ResourceRecords": [

                {
                    "Value": "..."
                },
                {
                    "Value": "..."
                }
            ],
            "Type": "NS",
            "Name": "my.domain.name.",
            "TTL": 172800
        }
    ]
}
```

v1.10.17

```
$ aws route53 list-resource-record-sets --hosted-zone-id $ZONE_ID \\
    --max-items 1 --starting-token 'my.domain.name.' --debug

Bad starting token: my.domain.name.
```

In this example, the use case is that the user wants to get information about a specific resource record set (in this case for the domain name of `my.domain.name.`).  This maps to the `StartRecordName` param name in the API.

Note: even though this is a CLI specific example, I'm filing it here because the fix for this issue will need to come from botocore.

diff --git a/botocore/paginate.py b/botocore/paginate.py
index ea2583d93..cb21d1949 100644
--- a/botocore/paginate.py
+++ b/botocore/paginate.py
@@ -379,8 +379,15 @@ class PageIterator(object):
         This attempts to convert a deprecated starting token into the new
         style.
         """
-        if len(deprecated_token) != len(self._input_token):
+        len_deprecated_token = len(deprecated_token)
+        len_input_token = len(self._input_token)
+        if len_deprecated_token > len_input_token:
             raise ValueError("Bad starting token: %s" % self._starting_token)
+        elif len_deprecated_token < len_input_token:
+            log.debug("Old format starting token does not contain all input "
+                      "tokens. Setting the rest, in order, as None.")
+            for i in range(len_input_token - len_deprecated_token):
+                deprecated_token.append(None)
         return dict(zip(self._input_token, deprecated_token))
 
 
diff --git a/tests/integration/test_route53.py b/tests/integration/test_route53.py
index ff98b10b0..95caec4a2 100644
--- a/tests/integration/test_route53.py
+++ b/tests/integration/test_route53.py
@@ -15,9 +15,10 @@ import unittest
 import itertools
 
 import botocore.session
+from botocore.exceptions import ClientError
 
 
-class TestRDSPagination(unittest.TestCase):
+class TestRoute53Pagination(unittest.TestCase):
     def setUp(self):
         self.session = botocore.session.get_session()
         self.client = self.session.create_client('route53', 'us-west-2')
@@ -29,6 +30,22 @@ class TestRDSPagination(unittest.TestCase):
         results = list(paginator.paginate(PaginationConfig={'MaxItems': '1'}))
         self.assertTrue(len(results) >= 0)
 
+    def test_paginate_with_deprecated_paginator_and_limited_input_tokens(self):
+        paginator = self.client.get_paginator('list_resource_record_sets')
+
+        # We're making sure the paginator gets set without failing locally, so
+        # a ClientError is acceptable. In this case, the Hosted Zone specified
+        # does not exist.
+        with self.assertRaises(ClientError):
+            results = list(paginator.paginate(
+                PaginationConfig={
+                    'MaxItems': '1',
+                    'StartingToken': 'my.domain.name.'
+                },
+                HostedZoneId="foo"
+            ))
+            self.assertTrue(len(results) >= 0)
+
 
 if __name__ == '__main__':
     unittest.main()
diff --git a/tests/unit/test_paginate.py b/tests/unit/test_paginate.py
index 463df478a..bf20746eb 100644
--- a/tests/unit/test_paginate.py
+++ b/tests/unit/test_paginate.py
@@ -978,6 +978,50 @@ class TestDeprecatedStartingToken(unittest.TestCase):
         }
         self.assert_pagination_result(expected, pagination_config)
 
+    def test_deprecated_starting_token_without_all_input_set_to_none(self):
+        responses = [
+            {
+                "Users": ["User1", "User2"],
+                "Groups": ["Group1"],
+                "Marker1": "m1",
+                "Marker2": "m2"
+            },
+            {
+                "Users": ["User3", "User4"],
+                "Groups": ["Group2"],
+                "Marker1": "m3",
+                "Marker2": "m4"
+            },
+            {
+                "Users": ["User5"],
+                "Groups": ["Group3"]
+            }
+        ]
+        self.method.side_effect = responses
+        pagination_config = {'StartingToken': 'm0'}
+        expected = {
+            'Groups': ['Group2', 'Group3'],
+            'Users': ['User1', 'User2', 'User3', 'User4', 'User5']
+        }
+        self.assert_pagination_result(
+            expected, pagination_config, multiple_tokens=True)
+
+    def test_deprecated_starting_token_rejects_too_many_input_tokens(self):
+        responses = [
+            {"Users": ["User1"], "Marker": "m2"},
+            {"Users": ["User2"], "Marker": "m3"},
+            {"Users": ["User3"]},
+        ]
+        self.method.side_effect = responses
+        pagination_config = {'StartingToken': 'm1___m4___0'}
+        expected = {'Users': ['User1', 'User2', 'User3']}
+
+        paginator = self.create_paginator()
+        with self.assertRaises(ValueError):
+            actual = paginator.paginate(
+                PaginationConfig=pagination_config).build_full_result()
+            self.assertEqual(actual, expected)
+
 
 if __name__ == '__main__':
     unittest.main()
['botocore/paginate.py', 'tests/unit/test_paginate.py', 'tests/integration/test_route53.py']