ok, first of all I would like to say I'm a regex IDIOT!. That being said, here's what I got:

RewriteEngine On
RewriteRule ^/([^/\.]+)/deals/([^/\.]+)/?$ index.php?key=$1&permalink=$2

What I'm trying to do is match the following url request paths:

/key-goes-here/deals/permalink-goes-here
/key-goes-here/deals/permalink-goes-here/

The string will always start with / 
The string may or may not end with /
The "key-goes-here" part will always be alphanumeric and - (hyphens to separate words)
The "permalink-goes-here" part will always be alphanumeric and - (hyphens to separate words) 

Thanks in advance

Using RegexBuddy

\/.+\/deals\/.+

RewriteRule ^([^/.]+)/deals/([^\.]+)/?$ /index.php?key=$1&permalink=$2 [L]

Remove first slash. URL paths are localised "per directory" before being passed to mod_rewrite.

Don't escape period in character group.

Add the [L] flag.

Make sure rule is listed after rules which redirect.

The /? construct allows two URLs to serve the same content. This is a duplicate content problem  For pages, allow only the URL without slash to serve content. Set up another rule which redirects requests with slash to URL without slash.